lexbtree.h

lex语法分析

// LexBTree.h: interface for the CLexBTree class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_LEXBTREE_H__746CAD9F_E9B6_11D8_B47B_0000E8E7E526__INCLUDED_)
#define AFX_LEXBTREE_H__746CAD9F_E9B6_11D8_B47B_0000E8E7E526__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <string>
using namespace std;

/*
#define NIL_PTR  -1
#define WORDLEN 31
#define CELLNUM 2
#define PAGENUM 2

#define KEYNUM  2  
#define M  (KEYNUM+1)
// 调试的时候用2-3树(3阶B树)
#define NODENUM 100
*/


#define NIL_PTR  -1
#define WORDLEN 31
#define CELLNUM 40
#define PAGENUM 4096

#define KEYNUM  45  
#define M  (KEYNUM+1)
// 调试的时候用2-3树(3阶B树)
#define NODENUM 768




#define TAGNUM_IN_CELL 16
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//#define  KT_DIVISOR 60
//#define  KT_BASENUM 5
#define  KT_DIVISOR 35
#define  KT_BASENUM 6

class CKeyType
{
public:
	unsigned long high;
	unsigned long mid_high;
	unsigned long mid_low;
	unsigned long low;
	bool operator >  (const CKeyType& kt);
	bool operator >= (const CKeyType& kt);
	bool operator == (const CKeyType& kt);
	bool operator <  (const CKeyType& kt);
	bool operator <= (const CKeyType& kt);
	void operator =  (const CKeyType& kt);
	void operator =  (unsigned long n);
	CKeyType();
};
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

class CKeyValueError{
};
class CTagNumError{
};
class CNodeError {
};
// 此B树只有插入操作,没有删除操作
class CLexBTree  
{
	//
	// 下面用 _slot表示在本结构的数组成员的位置 (在内存中槽位) 是一直增长的
	// 下面用 _naddr表示页子在文件中的存储位置(用整数表示,真实位置为此整数乘以page的结构长度)
	//  _naddr 是以 页为单位的，其中加了个n就是这个含义
	//  
	// 单词存储    页子,  区域
	// 
	// 注意这些naddr,slot,ptr都是整数,常用做熟组的下标,都是从0开始记数的,
	// 所以开始赋值的时候 赋予NIL_PTR
	// raw_slot  赋予 0
public:
	struct SCell {
		char word[WORDLEN+1];
		unsigned int aryTag[TAGNUM_IN_CELL];
		// 注意tag是从 1 开始编号的，因为这样可以和
		// CLexBTree中的ClearCell一致
		// 0 表示此aryTag[i]未使用
		unsigned int  aryTagCount[TAGNUM_IN_CELL];
	};
	struct SPage {
		int   next_page_naddr; // 下一片页子在文件中的存储位置(用整数表示,真实位置为此整数乘以page的结构长度)
		                       // 使页在文件中是链式存储的
		int   used_cell_slot_sum;
		SCell cell_ary[CELLNUM];
	};  // page是存储到硬盘上的一个实体
	// 在PageArea中没有设page_slot 因为这里的page_slot是有NRU算法得到
	struct SPageArena {
		int  total_page;
		bool bDirty_ary[PAGENUM];  // 指出某个页子是不是被修改过，若修改过则在NRU调出时，写入硬盘
		int  access_ary[PAGENUM];  // 访问指示, 用于最长最久未使用的算法
		                           // 刚访问的赋值MAX_INT  值 -1 表示空白的页子
		int    page_naddr_ary[PAGENUM];
		SPage  page_ary[PAGENUM];
	};  // 这个用做缓存用于与硬盘中的缓冲,当没有内存中没有空白页子的时候,运用NRU算法
	    // 将内存中最长未使用的页子写入硬盘
	 
	// B 树 存储  节点,区域
	struct SNode {
		bool bDirty;           // 记录此节点是不是被修改过,当flush的时候决定是否写入
		bool bPtToPageNaddr;   // ptr是指向页子的吗
		int  used_key_slot_sum;
		int  ptr_o;            // 在TreeArea中的位置
		int  ptr_ary[KEYNUM];  // (用整数表示,真实位置为此整数乘以page的结构长度)
		                       // B树的最后一级存储的是页子的 _naddr
		CKeyType key_ary[KEYNUM];
	};
	struct SNodeArea {
		int root_node_slot;
		int used_node_slot_sum;
		SNode node_ary[NODENUM];
	};

public:
	bool Manipulate(string strWord,unsigned int nTag);
	void FlushToDict();
	void FlushToIdx();
	void FlushToDisk();
	void Clean();
	CLexBTree();
	virtual ~CLexBTree();
protected:
	SNodeArea*  m_pNodeArea;
	SPageArena* m_pPageArena;
	CFile*  m_pDictFile;
private:
	unsigned long m_ulBase[KT_BASENUM];  // 这个数组是用于计算键值的
private:

	int  GetParentNode(int son_ptr,bool bPtToPage);
	int  TraverseSearchParent(int root,int son_ptr,bool bPtToPage);
	void BuildCell(string strWord,unsigned int nTag, SCell &cell);
	void BuildOneCellPage(string strWord,unsigned int nTag, SPage &page);
	bool XeroxCellToNotFullPage(SCell cell,SPage* pPage,int ins_cell_slot);
	void CopyCell(SCell* pSrcCell,SCell* pDestCell);
	void CopyPage(SPage *pSrcPage, SPage *pDestPage);
	bool CopyPageByRange(SPage* pSrcPage,SPage& pageDest,int start_cell_slot,int sum);
	void ClearCell(SCell *pCell);
	void ClearPage(SPage *pPage);
	void WriteAndClearPageSlot(int page_slot);
	void WriteNotClearPageSlot(int page_slot);
	void ReadAndSetPageSlot(int from_page_addr,int to_page_slot);
	void InsertKeyToBTree(CKeyType fKey,int ptr, int node_slot);
	bool InsertKeyToNotFullNode(CKeyType fKey,int ptr, SNode *pNode);
	int  GetSparePageSlotByNRU();
	int  GetSpareNodeSlot();
	int  SearchPageNaddr(CKeyType fKey);
	void SubAllPageAccessCount();
	CKeyType BirthKey(string strWord);
	int  CeilInt(int a,int b);
	int  CeilInt2(int a,int b);

	void CopyNode(SNode *pSrcNode, SNode *pDestNode);
	void ClearNode(SNode *pNode);
	bool CopyNodeByRange(SNode* pSrcNode,SNode& nodeDest,int start_key_slot,int sum);
	void CreateNewRootNodeWithOneKey(int ptr_l,CKeyType key,int ptr_r);
	void CreateFirstPageFirstNodeWithOnePtr(string strWord,unsigned int nTag);
	void AddTagCountToThisCell(SCell* pCell,const unsigned int nTag);
protected:
	void InsertToPage(string strWord,unsigned int nTag, int page_slot,int ins_cell_slot);
	int  ObtainPageSlot(string strWord);
	bool Match(string strWord,unsigned int nTag, const int page_slot,int& ins_cell_slot);
};

#endif // !defined(AFX_LEXBTREE_H__746CAD9F_E9B6_11D8_B47B_0000E8E7E526__INCLUDED_)