zbtree.cpp

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

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

** Filename : ZBtree.cpp

** Copyright (c) 2001-2002 Computer Science & Technology Zhejiang University 

** Editor   : zhousen(周森)

** Date     : 2001-12-18 To 2002-01-05

** Version  : 1.00

******************************************************************/
#include "ZBTree.h"
#include "Glob_Var.h"

extern unsigned int BTreeNodeSize;
extern _M_Buffer Buffer;
extern unsigned int  SizeOfPageHead;
extern char CurLocation[256];
extern char CurRelationName[33];

//-------------------------------ZBTree_Index--------------------------------------
ZBTree_Index::ZBTree_Index()
{
  
}

ZBTree_Index::~ZBTree_Index()
{
  
}

// produce the information in the IdxHead
void ZBTree_Index::Create_Head(char* KeyStr)
{
  SetKeyInfo(KeyStr);    // calculate the Keysize and KeyAttrNum
  // calculate the MaxItemNum in a node
  // Next_Empty_Block | IsLeaf | ItemOnNode | p[0],k[0],...,p[MaxItemNum] 
  IdxHead.MaxItemNum = ( BTreeNodeSize - 2*sizeof(_F_FileAddr) - sizeof(bool) - sizeof(int) ) 
                       / ( sizeof(_F_FileAddr) + IdxHead.KeySize );
  
  //no empty block
  IdxHead.FirstEmptyBlock.ulFilePageID = 0;
  IdxHead.FirstEmptyBlock.uiOffset     = 0; 
  IdxHead.LastEmptyBlock.ulFilePageID  = 0;
  IdxHead.LastEmptyBlock.uiOffset      = 0;
  
  //the first address of the BTree node
  IdxHead.FirstNewBlock.ulFilePageID = 1;
  IdxHead.FirstNewBlock.uiOffset     = SizeOfPageHead + BTreeNodeSize;

  // initialize the root address 
  IdxHead.root.ulFilePageID = 1;
  IdxHead.root.uiOffset     = SizeOfPageHead;
  
  // the start node isn't existed
  IdxHead.start.ulFilePageID = 0;
  IdxHead.start.uiOffset     = 0;

  // the key information
  KeyInfo = KeyStr;
}

// write the infomation to the head of the btree index file
void ZBTree_Index::WriteHeadToFile()
{
  // get the start address which store the head
  char address[256];
  strcpy(address,CurLocation);
  strcat(address,CurRelationName);
  strcat(address,".idx");
  _M_File test = Buffer[address];  
  _F_FileAddr ptr = test.GetIdxPoint();

  // write IdxHead
  void* temp = (void*)(&IdxHead);
  _F_FileAddr next;
  next = MemWrite( temp,sizeof(Index_Head),&ptr);
 
  // write Key information
  temp = (void*)KeyInfo;
  
  MemWrite(temp,strlen(KeyInfo) + 1,&next);
}

// read the infomation from the head of the btree index file
void ZBTree_Index::ReadHeadFromFile()
{
  // get the start address which store the head
  char address[256];
  strcpy(address,CurLocation);
  strcat(address,CurRelationName);
  strcat(address,".idx");
  _M_File test = Buffer[address];  
  _F_FileAddr ptr = test.GetIdxPoint();

  // read IdxHead
  Index_Head* temp;
  temp = (Index_Head*) ( ptr.MemAddr() );
  IdxHead = *temp;

  // read key information
  ptr.ShiftOffset(sizeof(Index_Head));
  KeyInfo = (char*) (ptr.MemAddr());
 
}
 

// calculate the KeySize and count the KeyAttrNum
void ZBTree_Index::SetKeyInfo(char* KeyStr)
{
  IdxHead.KeyAttrNum = 0;		 // the number of fields(attributes) in primary key
  IdxHead.KeySize    = 0;    // sizeof(Key_Attr) * KeyAttrNum
  char* temp = KeyStr;
  for( int i=0; temp[i]!=0; i++)
  {
    IdxHead.KeyAttrNum++;
    switch(temp[i])
    {
      case 'i' : IdxHead.KeySize += sizeof(int);     break;
      case 'f' : IdxHead.KeySize += sizeof(float);   break;
      case 'c' : {
                   //deal with the max length in a string defined by the user
                   int num = 0;
                   for( i=i+1; isdigit(temp[i]); i++)
                   {
                     num = num * 10 + temp[i] - '0';
                   }
                   i--;        // move the index back
                   num++;      // for '\0' which is the end of a string
                   IdxHead.KeySize += num;
                   break;
                 }
      default  : throw(1021);  //1021 字段类行错误

    }
  }

}

// return the size of key
int ZBTree_Index::GetKeySize()
{
  return IdxHead.KeySize;
}

// return the number of attribute in a key
int ZBTree_Index::GetKeyAttrNum()
{
  return IdxHead.KeyAttrNum;
} 

// return the max number of items in a btree node
int ZBTree_Index::GetMaxItemNum()
{
  return IdxHead.MaxItemNum;
}
 
// return the file point of the root
_F_FileAddr ZBTree_Index::GetRoot()
{
  return IdxHead.root;
}

// return the file point of the fisrt leaf node
_F_FileAddr ZBTree_Index::GetStartNode()
{
  return IdxHead.start;
}

// return the key information
char* ZBTree_Index::GetKeyInfo()
{
  return KeyInfo;
}

//-------------------------------ZBTree_Index--------------------------------------

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

// initialize the node 
ZBTree_Node::ZBTree_Node()
{
  // read the head of the file
  ZBTree_Index temp;
  temp.ReadHeadFromFile();

  MaxItem    = temp.GetMaxItemNum();  // get the MaxItem
  KeyInfo    = temp.GetKeyInfo();     // get the KeyInfo
  KeySize    = temp.GetKeySize();     // get the size of key
  ItemOnNode = 0;                     // the key number is 0
  
  p = new _F_FileAddr[MaxItem+1];
  for(int i=0;i<MaxItem+1;i++)
  {
    p[i].ulFilePageID = 0;
    p[i].uiOffset     = 0;
  }

  k = new pKey_Attr[MaxItem];
  for(int j=0;j<MaxItem;j++)
    k[j] = NULL; 
}

// set all k[i] to NULL
void ZBTree_Node::Reset()
{
  for(int j=0;j<ItemOnNode;j++)
    k[j] = NULL; 
  ItemOnNode = 0;
}

// write the separate space into one block
// MemPtr is the first address of the block
void ZBTree_Node::WriteNodeToFile(_F_FileAddr ptr)
{
  void* MemPtr;
  MemPtr = ptr.MemAddr();
  
  // write Next_Empty_Block into the block
  MemWrite((void*)(&Next_Empty_Block),sizeof(_F_FileAddr),&ptr);
  // move to the first address of IsLeaf
  MemPtr = (void*)((char*)MemPtr + sizeof(_F_FileAddr));
  
  // write IsLeaf into the block
  bool* pIsLeaf = (bool*)MemPtr;
  *pIsLeaf      = IsLeaf;
       
  // move to the first address of ItemNode in the block
  MemPtr = (void*)((char*)MemPtr + sizeof(bool));

  // write ItemOnNode into the block
  int *pItemOnNode = (int*)MemPtr;
  *pItemOnNode     = ItemOnNode;

  // move the the first address of p[o] in the block
  MemPtr = (void*)((char*)MemPtr + sizeof(int));

  int i;
  for(i=0;i<ItemOnNode;i++)
  {
    // write the p[i]
    _F_FileAddr* pp    = (_F_FileAddr*)MemPtr;
    pp->ulFilePageID = p[i].ulFilePageID;
    pp->uiOffset     = p[i].uiOffset;

    // move to the first address of k[i] in the block
    MemPtr = (void*)((char*)MemPtr + sizeof(_F_FileAddr));
    
    // write the k[i]
    pKey_Attr pField = k[i];
    for(int j=0;KeyInfo[j]!=0;j++)
    {
      switch(KeyInfo[j])
      {
        
        case 'i'   :  // int value
                      int *pIntValue;
                      pIntValue = (int*)MemPtr;
                      *pIntValue     = pField->value.IntValue;
                      pField         = pField->next;
                      MemPtr = (void*)((char*)MemPtr + sizeof(int));
                      break;
        case 'f'   :  // float value
                      float *pFloatValue; 
                      pFloatValue = (float*)MemPtr;
                      *pFloatValue       = pField->value.FloatValue;
                      pField             = pField->next;
                      MemPtr = (void*)((char*)MemPtr + sizeof(float));
                      break;
        case 'c'   :  // string
                      int num = 0;
                      for(j=j+1; isdigit(KeyInfo[j]);j++)
                      {
                        num = num * 10 + KeyInfo[j] - '0';
                      }
                      j--;        // move the index back
                      num++;      // for '\0' which is the end of a string
                      char* pCharValue = (char*)MemPtr;
                      strcpy(pCharValue,pField->value.pCharValue);
                      pField = pField->next;
                      MemPtr = (void*)((char*)MemPtr + num);
                      break;                      
      }
    }// KeyInfo[i] = '\0'
  }// i = ItemOnNode

  if( 0 == IsLeaf) // not a leaf
  {
    //Write the p[ItemOnNode]
    _F_FileAddr* pp = (_F_FileAddr*)MemPtr;
    pp->ulFilePageID = p[i].ulFilePageID;
    pp->uiOffset     = p[i].uiOffset;
  }
  else // is is a leaf
  {
    // move to the address of p[MaxItem]
    MemPtr = (void*)( (char*)MemPtr + (MaxItem - ItemOnNode) * (KeySize + sizeof(_F_FileAddr)) );
    //Write the p[MaxItem] into the block
    _F_FileAddr* pp = (_F_FileAddr*)MemPtr;
    pp->ulFilePageID = p[MaxItem].ulFilePageID;
    pp->uiOffset     = p[MaxItem].uiOffset;
  }
}

// the struct of node
// NodeType | ItemOnNode | p[0],k[0],p[1],k[1],......,p[MaxItem-1],k[MaxItem-1],p[MaxItem]
void ZBTree_Node::ReadNodeFromFile(_F_FileAddr ptr)
{
  // move to the address of NodeType
  void* temp     = ptr.MemAddr();
  // get the Next_Empty_Block
  _F_FileAddr* pNext = (_F_FileAddr*)temp;
  Next_Empty_Block.ulFilePageID = pNext->ulFilePageID;
  Next_Empty_Block.uiOffset     = pNext->uiOffset;

  // move to the address of NodeType
  temp = (void*)((char*)temp + sizeof(_F_FileAddr));

  // get the NodeType
  bool* pIsLeaf = (bool*)temp;
  IsLeaf        = *pIsLeaf;

  // move to the address of ItemOnNode
  temp = (void*)((char*)temp + sizeof(bool));
  
  // get the ItemOnNode
  int* pItemOnNode = (int*)temp;
  ItemOnNode       = *pItemOnNode;

  // move to the first address of p[0]
  temp = (void*)((char*)temp + sizeof(int));

  // read p[i] and k[i]
  int i;
  for(i=0;i<ItemOnNode;i++)
  {
    // get the p[i]
    _F_FileAddr* pp;
    pp = (_F_FileAddr*)temp;
    p[i].ulFilePageID = pp->ulFilePageID;
    p[i].uiOffset     = pp->uiOffset;

    // move to the first address of k[i] in the block
    temp = (void*)((char*)temp + sizeof(_F_FileAddr));
        
    // get the k[i]
    pKey_Attr pField;
    for(int j=0; KeyInfo[j]!='\0';j++)
    {
      if(j == 0)    // the first node
        pField = k[i] = new Key_Attr;
      else
      {
        pField->next = new Key_Attr;
        pField       = pField->next;
      }
      switch(KeyInfo[j])
      {
        case 'i'  :  // int value  
                     int* pIntValue;
                     pIntValue              = (int*) temp;
                     pField->value.IntValue = *pIntValue;
                     pField->next           = NULL;
                     temp = (void*)((char*)temp + sizeof(int));
                     break;

        case 'f'  :  // float value 
                     float* pFloatValue;
                     pFloatValue              = (float*) temp;
                     pField->value.FloatValue = *pFloatValue;
                     pField->next             = NULL;
                     temp = (void*)((char*)temp + sizeof(float));
                     break;

        case 'c'  :  // string
                     int num = 0;
                     for( j=j+1; isdigit(KeyInfo[j]); j++)
                     {
                       num = num * 10 + KeyInfo[j] - '0';
                     }
                     j--;        // move the index back
                     num++;      // for '\0' which is the end of a string
                     char* pCharValue = new char [num];
                     char* str = (char*)temp;
                     strcpy(pCharValue,str);
                     pField->value.pCharValue = pCharValue;
                     pField->next             = NULL;
                     temp = (void*)((char*)temp + num);
                     break;                  
      }
    }  //KeyInfo[i] = '\0'
  } // i = ItemOnNode

  if( 0 == IsLeaf)
  {
    // get the p[ItemOnNode]
    _F_FileAddr* pp;
    pp = (_F_FileAddr*)temp;
    p[i].ulFilePageID = pp->ulFilePageID;
    p[i].uiOffset     = pp->uiOffset;
  }
  else
  {
    // move to the address of p[MaxItem]
    temp = (void*)( (char*)temp + (MaxItem - ItemOnNode) * (KeySize + sizeof(_F_FileAddr)) );
    // get the p[MaxItem]
    _F_FileAddr* pp;
    pp = (_F_FileAddr*)temp;
    p[MaxItem].ulFilePageID = pp->ulFilePageID;
    p[MaxItem].uiOffset     = pp->uiOffset;
  }
    
}

// delete the space allocate for the node
ZBTree_Node::~ZBTree_Node()
{
  // delete the link list of keys
  for(int i=0;i<ItemOnNode;i++)
  {
    pKey_Attr head,temp;
    head = temp = k[i];
    for(int j=0;KeyInfo[j]!=0;j++)
    {
      switch(KeyInfo[j])
      {
        case 'i' :  // int 
                    head = head->next;
                    delete temp;
                    temp = head;
                    break;
        case 'f' :  // float
                    head = head->next;
                    delete temp;
                    temp = head;
                    break;
        case 'c' :  // char
                    delete  [] (head->value.pCharValue);
                    head = head->next;
                    delete temp;
                    temp = head;
                    while(isdigit(KeyInfo[++j])) ;  //skip digital number
                    j--;
                    break;
      }
    }
  }
  // detele the array of p and k
  delete [] p ;
  delete [] k;
}

// compare the key1 and key2
// if Key1 is greater than key2,return 1
// if key1 is equal with key2, return 0
// if key1 is less than key2,return -1
int ZBTree_Node::Compare(pKey_Attr Key1,pKey_Attr Key2)
{
   
  for(int i=0;KeyInfo[i]!='\0';i++)
  {
    switch(KeyInfo[i])
    {
      case 'i' :  // int
               if(Key1->value.IntValue > Key2->value.IntValue)
                 return 1;
               else if(Key1->value.IntValue < Key2->value.IntValue)
                 return -1;
               else
                 break;
      case 'f' :  // float
               if(Key1->value.FloatValue > Key2->value.FloatValue)
                 return 1;
               else if(Key1->value.FloatValue < Key2->value.FloatValue)
                 return -1;
               else
                 break;
      case 'c' :
               while(isdigit(KeyInfo[++i])) ;  //skip digital number
                    i--;
               int temp = strcmp(Key1->value.pCharValue,Key2->value.pCharValue);
               if(temp == 0)  // equal 
                 break;
               else if(temp > 0)
                 return 1;
               else 
                 return -1;
                
    }
    Key1 = Key1->next;
    Key2 = Key2->next;    
  }
  return 0;  // the keys are equal
}


// insert a key in the node which isn a leaf
void ZBTree_Node::InsertKeyInLeaf(_F_FileAddr pRec,pKey_Attr pPrimKey)
{
  if( 0 == ItemOnNode )  // The node is empty
  {
    p[0] = pRec;
    k[0] = pPrimKey;
  }