buffer.cpp

实现一个精简型单用户SQL引擎(DBMS)MiniSQL

/****************************************************************** 

** 文件名: Buffer.cpp

** Copyright (c) 2001-2002 计算机99F MiniSQL开发小组其一 

** 创建人: 郭振宇

** 日  期: 2001-11-28

** 修改人: 郭振宇

** 日  期: 2002-01-05

** 描  述: 定义了MiniSQL buffer模块所有类和结构

** 版  本: 1.00

******************************************************************/

#include"Buffer.h"

//-------------------------------------------------------

_M_Buffer Buffer;
unsigned int SizeOfPageHead = sizeof(_TB_PAGEHEAD);
unsigned int BTreeNodeSize = (FILE_PAGESIZE - SizeOfPageHead)/4;

//-------------------------------------------------------

// 初始化
void _TB_PAGEHEAD::Initial(unsigned long mypageid,bool myisfixed)
{
    this->ulPageID = mypageid;
    this->bIsFixed = myisfixed;
}

//-------------------------------------------------------

// 初始化
void _TB_FILECOND::InitialFileCond()
{
    this->ulPageTotal = 1;
    this->DelFirst.Initialize();
    this->DelLast.Initialize();
    this->NewInsert.ulFilePageID = 1;
    this->NewInsert.uiOffset = SizeOfPageHead;
}

//-------------------------------------------------------

// 文件头信息(若页PageID==0,则有，否则返回空)
_TB_FILECOND* _M_Page::Ptr2FileCond()
{
    return (_TB_FILECOND* )((char*)this->Ptr2PageBegin + SizeOfPageHead);
}

//-------------------------------------------------------

// 成员初始化，开辟内存空间
_M_Page::_M_Page()
{
	this->Ptr2PageBegin = malloc(FILE_PAGESIZE);
    if(!this->Ptr2PageBegin)  throw 1000;   // 内存开辟失败
	this->Ptr2Head = (_TB_PAGEHEAD*)this->Ptr2PageBegin;
	this->ulFilePageID = 0;
	this->uiFileID = 0;
}

//-------------------------------------------------------

// 释放内存空间
_M_Page::~_M_Page()
{
    this->ulFilePageID = 0;
	this->uiFileID = 0;
	free(this->Ptr2PageBegin);
    this->Ptr2Head = 0;
    this->Ptr2PageBegin = 0;
}

//-------------------------------------------------------

//**从文件中调入页至开辟好的内存空间中
void _M_Page::LoadFromFile(unsigned int fileid,unsigned long filepageid)
{
    this->uiFileID = fileid;
    this->ulFilePageID = filepageid;

    if( Buffer.GetIsNew(fileid) )   //  文件新建
    {
        this->Ptr2Head->Initial(filepageid,1);   // 初始化页头信息
        this->Ptr2FileCond()->InitialFileCond(); // 初始化文件头信息
        Buffer.SetIsNew(fileid,0);               // 设置使文件不再为新建状态(以免下次访问这个内存页又要进行头信息初始化)
    }
    else if( filepageid >= Buffer.GetPageTotal(fileid) ) // 比现有文件总页面要多,那么开辟新的页面加到文件末尾
    {
        if( filepageid - Buffer.GetPageTotal(fileid) > 0) throw 1004; // 页编号比现有文件最后一个页编号+1 还要大(浪费磁盘空间)
        this->Ptr2Head->Initial(filepageid,0);   // 初始化页头信息
        Buffer.AddPageTotal(fileid,1);           // 使文件总页数加1
    }
    else     // 其他情况
    {
	    lseek(Buffer.GetPtr2File(fileid),filepageid*FILE_PAGESIZE,0);  // 定位到将要取出的文件页的首地址
	    int temp = read(Buffer.GetPtr2File(fileid),this->Ptr2PageBegin,FILE_PAGESIZE); // 读到内存中
        if( temp!= FILE_PAGESIZE )  throw 1031; // 读失败
    }
}

//-------------------------------------------------------

//**把内存中的页写回到文件中
void _M_Page::Back2File() const
{
    int temp = 0;
	temp = lseek(Buffer.GetPtr2File(this->uiFileID),this->ulFilePageID*FILE_PAGESIZE,0);
    if(temp==-1L) throw 1005; 
	temp = write(Buffer.GetPtr2File(this->uiFileID),this->Ptr2PageBegin,FILE_PAGESIZE); // 写回文件
    if(temp!= FILE_PAGESIZE) throw 1002;  // 写失败
}

//-------------------------------------------------------

// 成员初始化
_M_PageInfo::_M_PageInfo()
{
	this->bIsLastUsed = 0;
	this->bIsModified = 0;
	this->Ptr2Page = 0;
}

//-------------------------------------------------------

// 析构，根据bIsModified决定是否需要写会文件
_M_PageInfo::~_M_PageInfo()
{
    if(this->Ptr2Page){
        if(this->Ptr2Page->uiFileID && this->Ptr2Page->ulFilePageID==0)
            // 把文件页总数写到磁盘中,已备下次读取
            this->Ptr2Page->Ptr2FileCond()->ulPageTotal = Buffer.GetPageTotal(this->Ptr2Page->uiFileID);
        if(this->Ptr2Page->uiFileID && this->bIsModified){ // 若为脏页,写回
            this->Ptr2Page->Back2File();
        }
        delete this->Ptr2Page;
        this->Ptr2Page = 0;
    }
    this->bIsLastUsed = 0;
    this->bIsModified = 0;
}

//-------------------------------------------------------

// 页替换、开辟等
void _M_PageInfo::UpdatePageInfo(unsigned int fileid,unsigned long filepageid)
{
	if( this->bIsModified) // 若为脏页,写回
		this->Ptr2Page->Back2File();

	this->bIsLastUsed = 1;
	this->bIsModified = 0;
    if( !this->Ptr2Page ){ // 尚未开辟内存空间
		this->Ptr2Page = new _M_Page; // 新的内存页对象
    }
    
    // 若文件新建 或者 该页为文件第0页 后者 该页在原来文件中不存在 则要求写回
    if( Buffer.GetIsNew(fileid) || filepageid >= Buffer.GetPageTotal(fileid) || filepageid==0 )
        this->bIsModified = 1;
    
	this->Ptr2Page->LoadFromFile(fileid,filepageid);  // 读到内存中
}

//-------------------------------------------------------

// 取得文件头信息地址
_TB_FILECOND* _M_PageInfo::GetPtr2FileCond() const
{
    return this->Ptr2Page->Ptr2FileCond();
}

//-------------------------------------------------------

// 取得页头信息地址
_TB_PAGEHEAD* _M_PageInfo::GetPtr2Head() const
{
    return this->Ptr2Page->Ptr2Head;
}

//-------------------------------------------------------

// 取得所分配的内存页目前内容所属的文件编号
unsigned int _M_PageInfo::GetFileID() const
{
    return this->Ptr2Page->uiFileID;
}

//-------------------------------------------------------

// 设置新的文件编号(抛弃页时设为0即可)
void _M_PageInfo::SetFileID(unsigned int fileid)
{
  this->Ptr2Page->uiFileID = fileid;
}

//-------------------------------------------------------

// 取得所分配的内存页目前内容在文件中的页编号
unsigned long _M_PageInfo::GetFilePageID() const
{
    return this->Ptr2Page->ulFilePageID;
}

//-------------------------------------------------------

// 成员初始化
_M_Clock::_M_Clock()
{
	this->uiClockSize = MEM_PAGEAMOUNT;
	this->uiCurrClockPtr = 1;
	for(unsigned int i=0;i<=this->uiClockSize;i++)
	{
		this->Ptr2MemPageInfo[i] = new _M_PageInfo;
	}
}

//-------------------------------------------------------

// 析构
_M_Clock::~_M_Clock()
{
	for(unsigned int i=0;i<=this->uiClockSize;i++)
		delete this->Ptr2MemPageInfo[i] ;
}

//-------------------------------------------------------

//**查找Clock中尚未分配内存空间的页
unsigned int _M_Clock::GetNullPage()
{
    for(unsigned int i=this->uiCurrClockPtr;i<=this->uiClockSize;i++)
    {
        if( !this->Ptr2MemPageInfo[i]->Ptr2Page ) // 尚未分配内存页
        {
            this->uiCurrClockPtr = i;
            return this->uiCurrClockPtr;
        }
    }
    return 0;
}

//-------------------------------------------------------

//**查找Clock中已经被抛弃的页
unsigned int _M_Clock::GetFreePage()
{
    for(unsigned int i=1;i<=this->uiClockSize;i++)
    {
        // 被抛弃内存页已经把文件编号置为 0 做为标记
        if( this->Ptr2MemPageInfo[i]->Ptr2Page && !this->Ptr2MemPageInfo[i]->GetFileID() )
        {
            this->uiCurrClockPtr = i;
            return this->uiCurrClockPtr;
        }
    }
    return 0;
}

//-------------------------------------------------------

// 查找Clock中最近一页可被替换的页
unsigned int _M_Clock::GetSwapPage(unsigned int fileid)
{
    if(! this->GetFreePage() )   // 查找被抛弃的内存页
        // 查找Clock中最早打开的文件所占用的内存页,如果是常驻内存页则关闭该文件(该写回的写回)
	    if(! this->NR_Search(fileid) )
		    if(! this->U_M_Search(0,0,0) ) // 上次没有用,没有被修改,不变动bIsLastUsed,返回符合这样条件的内存页
			    if(! this->U_M_Search(0,1,1) ) // 上次没有用,有被修改,变动bIsLastUsed,返回符合这样条件的内存页
				    if(! this->U_M_Search(0,0,0) ) // 上次没有用,没有被修改,不变动bIsLastUsed,返回符合这样条件的内存页
					    	this->U_M_Search(0,1,1);  // 上次没有用,有被修改,变动bIsLastUsed,返回符合这样条件的内存页
	return this->uiCurrClockPtr;
}			

//-------------------------------------------------------

// 查找Clock中最早打开的文件所占用的内存页,如果是常驻内存页则关闭该文件(该写回的写回)
// 所有打开的文件已经由_M_Buffer类组织成链表
unsigned int _M_Clock::NR_Search(unsigned int tarfileid)
{
    unsigned int NR_FileIDTemp = 0;     // 临时文件编号
    unsigned int NR_FileID = 20000;     // 欲替换的内存页所属文件编号(程序运行期分配),20000为不可能的一个数字(打开20000个文件方有可能)
    unsigned int ClockPtr = 0;          // 与替换的页编号
    unsigned int relativefileid = Buffer[tarfileid]->GetRelativeFileID(); // 取得关联文件编号
	for(unsigned int i=1;i<=this->uiClockSize;i++)
	{
        NR_FileIDTemp = this->Ptr2MemPageInfo[i]->GetFileID();
        // 文件编号不能为当前文件编号及其关联文件的编号,在符合这个条件的基础上,文件编号越小,越早打开,所以更适合被替换
		if( NR_FileIDTemp < NR_FileID && NR_FileIDTemp != tarfileid && NR_FileIDTemp != relativefileid )
        {
            NR_FileID = NR_FileIDTemp;
            ClockPtr = i;
        }
	}
    if( NR_FileID != 20000 )
    {
        // 如果被替换页是第 0 页,则关闭该文件及其关联文件
        if( this->Ptr2MemPageInfo[ClockPtr]->GetFilePageID() == 0 )
            Buffer[NR_FileID]->Close();
        this->uiCurrClockPtr = ClockPtr;
        return this->uiCurrClockPtr;
    }
    else
	    return 0;
}

//-------------------------------------------------------

// Clock算法实现,通过U_M_Search()四次调用,完成Clock算法
unsigned int _M_Clock::U_M_Search(bool islastused,bool ismodified,bool changeused)
{
	for(unsigned int i=1;i<=this->uiClockSize;i++)
	{		
		if( this->Ptr2MemPageInfo[this->uiCurrClockPtr]->GetPtr2Head()->bIsFixed == 0 &&
			this->Ptr2MemPageInfo[this->uiCurrClockPtr]->bIsLastUsed == islastused &&
			this->Ptr2MemPageInfo[this->uiCurrClockPtr]->bIsModified == ismodified )
				return this->uiCurrClockPtr;
		else
		{	
			if( changeused ) this->Ptr2MemPageInfo[this->uiCurrClockPtr]->bIsLastUsed = 0;
			this->uiCurrClockPtr = (this->uiCurrClockPtr+1)%this->uiClockSize;
			if(!this->uiCurrClockPtr)
				this->uiCurrClockPtr = this->uiClockSize;
		}
	}
	return 0;
}

//-------------------------------------------------------

// 查找已经存在的页(假设要找的页已经存在的话)
unsigned int _M_Clock::GetExsitPage(unsigned int fileid,unsigned long filepageid)
{
	if( this->Ptr2MemPageInfo[this->uiCurrClockPtr]->Ptr2Page &&
		this->Ptr2MemPageInfo[this->uiCurrClockPtr]->GetFileID() == fileid &&
		this->Ptr2MemPageInfo[this->uiCurrClockPtr]->GetFilePageID() == filepageid )
		return this->uiCurrClockPtr;

	for(unsigned int i=1;i<=this->uiClockSize;i++)
	{
        if(!this->Ptr2MemPageInfo[i]->Ptr2Page) break;
		if( this->Ptr2MemPageInfo[i]->GetFileID() == fileid &&
			this->Ptr2MemPageInfo[i]->GetFilePageID() == filepageid )
		{
			this->uiCurrClockPtr = i;
			return this->uiCurrClockPtr;
		}
	}

	return 0;
}

//-------------------------------------------------------

// 根据文件编号和页号取得内存页(通过上面各种方法)
_M_PageInfo* _M_Clock::GetTargetPage(unsigned int fileid,unsigned long filepageid)
{
    unsigned int tempint = this->GetExsitPage(fileid,filepageid);  // 先找内存页是否已经存在
	if(tempint)	return this->Ptr2MemPageInfo[tempint];

	tempint = this->GetNullPage();         // 看看有没有空的内存页尚未开辟使用
    if(!tempint) tempint = this->GetSwapPage(fileid); // 得到替换页
	this->Ptr2MemPageInfo[tempint]->UpdatePageInfo(fileid,filepageid); // 调入文件页至内存,并更新相关信息

    return this->Ptr2MemPageInfo[tempint];
}

//-------------------------------------------------------

// 抛弃文件所属内存页(适用于欲删除一个文件的时候)
void _M_Clock::CloseFilePages(unsigned int fileid)
{
	for(unsigned int i=1;i<=this->uiClockSize;i++)
	{
        if( !this->Ptr2MemPageInfo[i]->Ptr2Page ) break;
		if( this->Ptr2MemPageInfo[i]->GetFileID() == fileid )
		{
            if( this->Ptr2MemPageInfo[i]->bIsModified )
                this->Ptr2MemPageInfo[i]->Ptr2Page->Back2File();
			this->Ptr2MemPageInfo[i]->bIsModified = 0;
            this->Ptr2MemPageInfo[i]->SetFileID(0);
		}
	}
	return;	
}

//-------------------------------------------------------

// 设置当前页使之为脏页
void _M_Clock::SetPageModified()
{
    this->Ptr2MemPageInfo[this->uiCurrClockPtr]->bIsModified = 1;
}

//-------------------------------------------------------

// 初始化,打开和新建文件,若当前文件开的太多,导致无法再打开新文件,可自动关闭最早打开的文件
_M_File::_M_File(const char *name,unsigned int fileid)
{
		this->uiFileID = fileid;
        this->IsNew = 0;
        this->ulPageTotal = 1;
		strcpy(this->FileName,name);
		this->Ptr2File = open(name,_O_BINARY|O_RDWR,0664); 
        if(this->Ptr2File==-1){ // 文件不存在
            this->Ptr2File = open(name,_O_BINARY|O_RDWR|O_CREAT,0664); // 新建文件(打开文件)
            if(this->Ptr2File==-1)  // 文件不能被打开(新建)
            {
                if( Buffer._F_First) 
                    Buffer._F_First->Close(); // 关闭最早打开的文件
                this->Ptr2File = open(name,_O_BINARY|O_RDWR|O_CREAT,0664); // 新建文件(打开文件)
			    if(this->Ptr2File==-1)  // 文件不能被新建(打开)
                    throw 1006; // 文件还是不能被打开(新建),可能为磁盘空间不足等意外
            }
            this->IsNew = 1;
        }
		this->_F_Next = 0;
}

//-------------------------------------------------------

// 取得相关文件,由于一个表包含两个文件(.idx,.dbf),故查找关联的文件编号
unsigned int _M_File::GetRelativeFileID() const
{