开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > 其他数据库 > 查看源码
BPTree.cpp
资源名称：minisqlc.rar　[点击查看]
上传用户：lkd6667
上传日期：2015-05-13
资源大小：1448k
文件大小：43k
源码类别：

其他数据库

开发平台：

C/C++

BPTree.cpp：源码内容
  1. //!BPTree.cpp   2007/6/28
  3. #include "BPtree.h"
  4. #include "Glob_Var.h"
  6. extern unsigned int BTreeNodeSize;
  7. extern _M_Buffer Buffer;
  8. extern unsigned int  SizeOfPageHead;
  9. extern char CurLocation[256];
  10. extern char CurRelationName[33];
  12. /*=========================================================================
  13. =========             definition for BPTree_Index             =============
  14. =========================================================================*/
  16. /////////////////////////////////////////////////////////////////////////////////////////////////////////
  17. //constructor and destructor
  18. BPTree_Index::BPTree_Index() { 
  19. }
  21. BPTree_Index::~BPTree_Index(){
  22. }
  24. /////////////////////////////////////////////////////////////////////////////////////////////////////////
  25. void BPTree_Index::createHead(char* KeyStr) {
  26.   setKeyInfo(KeyStr);    // calculate the Keysize and KeyAttrNum
  27.   // calculate the MaxItemNum in a node
  28.   // Next_Empty_Block | IsLeaf | ItemOnNode | p[0],k[0],...,p[MaxItemNum] 
  29.   IdxHead.MaxItemNum = ( BTreeNodeSize - 2*sizeof(_F_FileAddr) - sizeof(bool) - sizeof(int) ) 
  30.                        / ( sizeof(_F_FileAddr) + IdxHead.KeySize );
  31.   
  32.   //no empty block
  33.   IdxHead.FirstEmptyBlock.ulFilePageID = 0;
  34.   IdxHead.FirstEmptyBlock.uiOffset     = 0; 
  35.   IdxHead.LastEmptyBlock.ulFilePageID  = 0;
  36.   IdxHead.LastEmptyBlock.uiOffset      = 0;
  37.   
  38.   //the first address of the BTree node
  39.   IdxHead.FirstNewBlock.ulFilePageID = 1;
  40.   IdxHead.FirstNewBlock.uiOffset     = SizeOfPageHead + BTreeNodeSize;
  42.   // initialize the root address 
  43.   IdxHead.root.ulFilePageID = 1;
  44.   IdxHead.root.uiOffset     = SizeOfPageHead;
  45.   
  46.   // the start node isn't existed
  47.   IdxHead.start.ulFilePageID = 0;
  48.   IdxHead.start.uiOffset     = 0;
  50.   // the key information
  51.   KeyInfo = KeyStr;
  52. }
  54. ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  55. // write the infomation to the head of the btree index file
  56. void BPTree_Index::writeHeadToFile() {
  57.   // get the start address which store the head
  58.   char address[256];
  59.   strcpy(address,CurLocation);
  60.   strcat(address,CurRelationName);
  61.   strcat(address,".idx");
  62.   _M_File test = Buffer[address];  
  63.   _F_FileAddr ptr = test.GetIdxPoint();
  65.   // write IdxHead
  66.   void* temp = (void*)(&IdxHead);
  67.   _F_FileAddr next;
  68.   next = MemWrite( temp,sizeof(Index_Head),&ptr);
  69.  
  70.   // write Key information
  71.   temp = (void*)KeyInfo;
  72.   
  73.   MemWrite(temp,strlen(KeyInfo) + 1,&next);
  74. }
  76. ////////////////////////////////////////////////////////////////////////////////////////////////////////////
  77. // read the infomation from the head of the btree index file
  78. void BPTree_Index::readHeadFromFile() {
  79.   // get the start address which store the head
  80.   char address[256];
  81.   strcpy(address,CurLocation);
  82.   strcat(address,CurRelationName);
  83.   strcat(address,".idx");
  84.   _M_File test = Buffer[address];  
  85.   _F_FileAddr ptr = test.GetIdxPoint();
  87.   // read IdxHead
  88.   Index_Head* temp;
  89.   temp = (Index_Head*) ( ptr.MemAddr() );
  90.   IdxHead = *temp;
  92.   // read key information
  93.   ptr.ShiftOffset(sizeof(Index_Head));
  94.   KeyInfo = (char*) (ptr.MemAddr());
  95.  
  96. }
  97.  
  98. ////////////////////////////////////////////////////////////////////////////////////////////////////////////
  99. // calculate the KeySize and count the KeyAttrNum
  100. void BPTree_Index::setKeyInfo(char* KeyStr) {
  101.   IdxHead.KeyAttrNum = 0;  // the number of fields(attributes) in primary key
  102.   IdxHead.KeySize    = 0;    // sizeof(Key_Attr) * KeyAttrNum
  103.   char* temp = KeyStr;
  104.   for( int i=0; temp[i]!=0; i++)
  105.   {
  106.     IdxHead.KeyAttrNum++;
  107.     switch(temp[i])
  108.     {
  109.       case 'i' : IdxHead.KeySize += sizeof(int);     break;
  110.       case 'f' : IdxHead.KeySize += sizeof(float);   break;
  111.       case 'c' : {
  112.                    //deal with the max length in a string defined by the user
  113.                    int num = 0;
  114.                    for( i=i+1; isdigit(temp[i]); i++)
  115.                    {
  116.                      num = num * 10 + temp[i] - '0';
  117.                    }
  118.                    i--;        // move the index back
  119.                    num++;      // for '' which is the end of a string
  120.                    IdxHead.KeySize += num;
  121.                    break;
  122.                  }
  123.       default  : throw(1021); 
  125.     }
  126.   }
  128. }
  130. // /////////////////////////////////////////////////////////////////////////////////////////////////////////
  132. int BPTree_Index::getKeySize() {
  133.   return IdxHead.KeySize;
  134. }
  136. int BPTree_Index::getKeyAttrNum() {
  137.   return IdxHead.KeyAttrNum;
  138. } 
  140. int BPTree_Index::getMaxItemNum() {
  141.   return IdxHead.MaxItemNum;
  142. }
  143.  
  144. _F_FileAddr BPTree_Index::getRoot() {
  145.   return IdxHead.root;
  146. }
  148. _F_FileAddr BPTree_Index::getStartNode() {
  149.   return IdxHead.start;
  150. }
  152. char* BPTree_Index::getKeyInfo() {
  153.   return KeyInfo;
  154. }
  156. ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  158. /*=========================================================================
  159. =========              definition for BPTreeNode              =============
  160. =========================================================================*/
  162. /////////////////////////////////////////////////////////////////////////////////////////////
  164. // initialize the node 
  165. BPTreeNode::BPTreeNode() {
  166.   // read the head of the file
  167.   BPTree_Index temp;
  168.   temp.readHeadFromFile();
  170.   MaxItem    = temp.getMaxItemNum();  // get the MaxItem
  171.   KeyInfo    = temp.getKeyInfo();     // get the KeyInfo
  172.   KeySize    = temp.getKeySize();     // get the size of key
  173.   ItemOnNode = 0;                     // the key number is 0
  174.   
  175.   p = new _F_FileAddr[MaxItem+1];
  176.   for(int i=0;i<MaxItem+1;i++)
  177.   {
  178.     p[i].ulFilePageID = 0;
  179.     p[i].uiOffset     = 0;
  180.   }
  182.   k = new pKey_Attr[MaxItem];
  183.   for(int j=0;j<MaxItem;j++)
  184.     k[j] = NULL; 
  185. }
  187. ///////////////////////////////////////////////////////////////////////////////////////////////
  188. void BPTreeNode::initialize() {
  189.   for(int j=0;j<ItemOnNode;j++)
  190.     k[j] = NULL; 
  191.   ItemOnNode = 0;
  192. }
  194. ///////////////////////////////////////////////////////////////////////////////////////////////
  195. // write the separate space into one block
  196. // MemPtr is the first address of the block
  197. void BPTreeNode::writeNodeToFile(_F_FileAddr ptr) {
  198.   void* MemPtr;
  199.   MemPtr = ptr.MemAddr();
  200.   
  201.   // write Next_Empty_Block into the block
  202.   MemWrite((void*)(&Next_Empty_Block),sizeof(_F_FileAddr),&ptr);
  203.   // move to the first address of IsLeaf
  204.   MemPtr = (void*)((char*)MemPtr + sizeof(_F_FileAddr));
  205.   
  206.   // write IsLeaf into the block
  207.   bool* pIsLeaf = (bool*)MemPtr;
  208.   *pIsLeaf      = IsLeaf;
  209.        
  210.   // move to the first address of ItemNode in the block
  211.   MemPtr = (void*)((char*)MemPtr + sizeof(bool));
  213.   // write ItemOnNode into the block
  214.   int *pItemOnNode = (int*)MemPtr;
  215.   *pItemOnNode     = ItemOnNode;
  217.   // move the the first address of p[o] in the block
  218.   MemPtr = (void*)((char*)MemPtr + sizeof(int));
  220.   int i;
  221.   for(i=0;i<ItemOnNode;i++)
  222.   {
  223.     // write the p[i]
  224.     _F_FileAddr* pp    = (_F_FileAddr*)MemPtr;
  225.     pp->ulFilePageID = p[i].ulFilePageID;
  226.     pp->uiOffset     = p[i].uiOffset;
  228.     // move to the first address of k[i] in the block
  229.     MemPtr = (void*)((char*)MemPtr + sizeof(_F_FileAddr));
  230.     
  231.     // write the k[i]
  232.     pKey_Attr pField = k[i];
  233.     for(int j=0;KeyInfo[j]!=0;j++)
  234.     {
  235.       switch(KeyInfo[j])
  236.       {
  237.         
  238.         case 'i'   :  // int value
  239.                       int *pIntValue;
  240.                       pIntValue = (int*)MemPtr;
  241.                       *pIntValue     = pField->value.IntValue;
  242.                       pField         = pField->next;
  243.                       MemPtr = (void*)((char*)MemPtr + sizeof(int));
  244.                       break;
  245.         case 'f'   :  // float value
  246.                       float *pFloatValue; 
  247.                       pFloatValue = (float*)MemPtr;
  248.                       *pFloatValue       = pField->value.FloatValue;
  249.                       pField             = pField->next;
  250.                       MemPtr = (void*)((char*)MemPtr + sizeof(float));
  251.                       break;
  252.         case 'c'   :  // string
  253.                       int num = 0;
  254.                       for(j=j+1; isdigit(KeyInfo[j]);j++)
  255.                       {
  256.                         num = num * 10 + KeyInfo[j] - '0';
  257.                       }
  258.                       j--;        // move the index back
  259.                       num++;      // for '' which is the end of a string
  260.                       char* pCharValue = (char*)MemPtr;
  261.                       strcpy(pCharValue,pField->value.pCharValue);
  262.                       pField = pField->next;
  263.                       MemPtr = (void*)((char*)MemPtr + num);
  264.                       break;                      
  265.       }
  266.     }// KeyInfo[i] = ''
  267.   }// i = ItemOnNode
  269.   if( 0 == IsLeaf) // not a leaf
  270.   {
  271.     //Write the p[ItemOnNode]
  272.     _F_FileAddr* pp = (_F_FileAddr*)MemPtr;
  273.     pp->ulFilePageID = p[i].ulFilePageID;
  274.     pp->uiOffset     = p[i].uiOffset;
  275.   }
  276.   else // is is a leaf
  277.   {
  278.     // move to the address of p[MaxItem]
  279.     MemPtr = (void*)( (char*)MemPtr + (MaxItem - ItemOnNode) * (KeySize + sizeof(_F_FileAddr)) );
  280.     //Write the p[MaxItem] into the block
  281.     _F_FileAddr* pp = (_F_FileAddr*)MemPtr;
  282.     pp->ulFilePageID = p[MaxItem].ulFilePageID;
  283.     pp->uiOffset     = p[MaxItem].uiOffset;
  284.   }
  285. }
  287. ///////////////////////////////////////////////////////////////////////////////////////////////
  288. // the struct of node
  289. // NodeType | ItemOnNode | p[0],k[0],p[1],k[1],......,p[MaxItem-1],k[MaxItem-1],p[MaxItem]
  290. void BPTreeNode::readNodeFromFile(_F_FileAddr ptr) {
  291.   // move to the address of NodeType
  292.   void* temp     = ptr.MemAddr();
  293.   // get the Next_Empty_Block
  294.   _F_FileAddr* pNext = (_F_FileAddr*)temp;
  295.   Next_Empty_Block.ulFilePageID = pNext->ulFilePageID;
  296.   Next_Empty_Block.uiOffset     = pNext->uiOffset;
  298.   // move to the address of NodeType
  299.   temp = (void*)((char*)temp + sizeof(_F_FileAddr));
  301.   // get the NodeType
  302.   bool* pIsLeaf = (bool*)temp;
  303.   IsLeaf        = *pIsLeaf;
  305.   // move to the address of ItemOnNode
  306.   temp = (void*)((char*)temp + sizeof(bool));
  307.   
  308.   // get the ItemOnNode
  309.   int* pItemOnNode = (int*)temp;
  310.   ItemOnNode       = *pItemOnNode;
  312.   // move to the first address of p[0]
  313.   temp = (void*)((char*)temp + sizeof(int));
  315.   // read p[i] and k[i]
  316.   int i;
  317.   for(i=0;i<ItemOnNode;i++)
  318.   {
  319.     // get the p[i]
  320.     _F_FileAddr* pp;
  321.     pp = (_F_FileAddr*)temp;
  322.     p[i].ulFilePageID = pp->ulFilePageID;
  323.     p[i].uiOffset     = pp->uiOffset;
  325.     // move to the first address of k[i] in the block
  326.     temp = (void*)((char*)temp + sizeof(_F_FileAddr));
  327.         
  328.     // get the k[i]
  329.     pKey_Attr pField;
  330.     for(int j=0; KeyInfo[j]!='';j++)
  331.     {
  332.       if(j == 0)    // the first node
  333.         pField = k[i] = new Key_Attr;
  334.       else
  335.       {
  336.         pField->next = new Key_Attr;
  337.         pField       = pField->next;
  338.       }
  339.       switch(KeyInfo[j])
  340.       {
  341.         case 'i'  :  // int value  
  342.                      int* pIntValue;
  343.                      pIntValue              = (int*) temp;
  344.                      pField->value.IntValue = *pIntValue;
  345.                      pField->next           = NULL;
  346.                      temp = (void*)((char*)temp + sizeof(int));
  347.                      break;
  349.         case 'f'  :  // float value 
  350.                      float* pFloatValue;
  351.                      pFloatValue              = (float*) temp;
  352.                      pField->value.FloatValue = *pFloatValue;
  353.                      pField->next             = NULL;
  354.                      temp = (void*)((char*)temp + sizeof(float));
  355.                      break;
  357.         case 'c'  :  // string
  358.                      int num = 0;
  359.                      for( j=j+1; isdigit(KeyInfo[j]); j++)
  360.                      {
  361.                        num = num * 10 + KeyInfo[j] - '0';
  362.                      }
  363.                      j--;        // move the index back
  364.                      num++;      // for '' which is the end of a string
  365.                      char* pCharValue = new char [num];
  366.                      char* str = (char*)temp;
  367.                      strcpy(pCharValue,str);
  368.                      pField->value.pCharValue = pCharValue;
  369.                      pField->next             = NULL;
  370.                      temp = (void*)((char*)temp + num);
  371.                      break;                  
  372.       }
  373.     }  //KeyInfo[i] = ''
  374.   } // i = ItemOnNode
  376.   if( 0 == IsLeaf)
  377.   {
  378.     // get the p[ItemOnNode]
  379.     _F_FileAddr* pp;
  380.     pp = (_F_FileAddr*)temp;
  381.     p[i].ulFilePageID = pp->ulFilePageID;
  382.     p[i].uiOffset     = pp->uiOffset;
  383.   }
  384.   else
  385.   {
  386.     // move to the address of p[MaxItem]
  387.     temp = (void*)( (char*)temp + (MaxItem - ItemOnNode) * (KeySize + sizeof(_F_FileAddr)) );
  388.     // get the p[MaxItem]
  389.     _F_FileAddr* pp;
  390.     pp = (_F_FileAddr*)temp;
  391.     p[MaxItem].ulFilePageID = pp->ulFilePageID;
  392.     p[MaxItem].uiOffset     = pp->uiOffset;
  393.   }
  394.     
  395. }
  397. ///////////////////////////////////////////////////////////////////////////////////////////////
  398. // delete the space allocate for the node
  399. BPTreeNode::~BPTreeNode() {
  400.   // delete the link list of keys
  401.   for(int i=0;i<ItemOnNode;i++)
  402.   {
  403.     pKey_Attr head,temp;
  404.     head = temp = k[i];
  405.     for(int j=0;KeyInfo[j]!=0;j++)
  406.     {
  407.       switch(KeyInfo[j])
  408.       {
  409.         case 'i' :  // int 
  410.                     head = head->next;
  411.                     delete temp;
  412.                     temp = head;
  413.                     break;
  414.         case 'f' :  // float
  415.                     head = head->next;
  416.                     delete temp;
  417.                     temp = head;
  418.                     break;
  419.         case 'c' :  // char
  420.                     delete  [] (head->value.pCharValue);
  421.                     head = head->next;
  422.                     delete temp;
  423.                     temp = head;
  424.                     while(isdigit(KeyInfo[++j])) ;  //skip digital number
  425.                     j--;
  426.                     break;
  427.       }
  428.     }
  429.   }
  430.   // detele the array of p and k
  431.   delete [] p ;
  432.   delete [] k;
  433. }
  434. ///////////////////////////////////////////////////////////////////////////////////////////////
  435. // compare the key1 and key2
  436. // if Key1 is greater than key2,return 1
  437. // if key1 is equal with key2, return 0
  438. // if key1 is less than key2,return -1
  439. int BPTreeNode::compare(pKey_Attr Key1,pKey_Attr Key2) {
  440.    
  441.   for(int i=0;KeyInfo[i]!='';i++)
  442.   {
  443.     switch(KeyInfo[i])
  444.     {
  445.   case 'i' :
  446.                if(Key1->value.IntValue > Key2->value.IntValue)
  447.                  return 1;
  448.                else if(Key1->value.IntValue < Key2->value.IntValue)
  449.                  return -1;
  450.                else
  451.                  break;
  452.       case 'f' : 
  453.                if(Key1->value.FloatValue > Key2->value.FloatValue)
  454.                  return 1;
  455.                else if(Key1->value.FloatValue < Key2->value.FloatValue)
  456.                  return -1;
  457.                else
  458.                  break;
  459.       case 'c' :
  460.                while(isdigit(KeyInfo[++i])) ;
  461.                     i--;
  462.                int temp = strcmp(Key1->value.pCharValue,Key2->value.pCharValue);
  463.                if(temp == 0) 
  464.                  break;
  465.                else if(temp > 0)
  466.                  return 1;
  467.                else 
  468.                  return -1;
  469.                 
  470.     }
  471.     Key1 = Key1->next;
  472.     Key2 = Key2->next;    
  473.   }
  474.   return 0;
  475. }
  477. ///////////////////////////////////////////////////////////////////////////////////////////////
  478. // insert a key in the node which isn a leaf
  479. void BPTreeNode::insertKeyInLeaf(_F_FileAddr pRec,pKey_Attr pPrimKey) {
  480.   if( 0 == ItemOnNode )  // The node is empty
  481.   {
  482.     p[0] = pRec;
  483.     k[0] = pPrimKey;
  484.   }
  485. //  p[ItemOnNode + 1] = p[ItemOnNode];
  486.   for(int i=ItemOnNode-1;i>=0;i--)
  487.   {
  488.     if(compare(pPrimKey,k[i]) < 0)
  489.     {
  490.       p[i+1] = p[i];
  491.       k[i+1] = k[i];
  492.       continue;
  493.     }
  494.     else 
  495.       break;
  496.   }
  497.   p[i+1] = pRec;
  498.   k[i+1] = pPrimKey;
  499.   ItemOnNode++;
  500. }
  501. ///////////////////////////////////////////////////////////////////////////////////////////////
  502. // insert a key in the node which isn't a leaf
  503. void BPTreeNode::insertKeyNotLeaf(pKey_Attr pPrimKey,_F_FileAddr pRec) {
  504.   // the node is never empty
  505.   for(int i=ItemOnNode-1;i>=0;i--)
  506.   {
  507.     if(compare(pPrimKey,k[i]) < 0)
  508.     {
  509.       p[i+2] = p[i+1];
  510.       k[i+1] = k[i];
  511.       continue;
  512.     }
  513.     else 
  514.       break;
  515.   }
  516.   p[i+2] = pRec;
  517.   k[i+1] = pPrimKey;
  518.   ItemOnNode++;
  519. }
  521. ///////////////////////////////////////////////////////////////////////////////////////////////
  522. // delete a key in a leaf and adjust the node
  523. void BPTreeNode::deleteKeyInLeaf(pKey_Attr pPrimKey) {
  524.   int i;
  525.   for(i=0;i<ItemOnNode;i++)
  526.   {
  527.     if( compare(pPrimKey,k[i]) == 0 )
  528.       break;
  529.   }
  530.   deleteKeySpace(k[i]);  // delete the space of k[i]
  531.   // adjust the node
  532.   for(;i<ItemOnNode-1;i++)
  533.   {
  534.     p[i] = p[i+1];
  535.     k[i] = k[i+1];
  536.   }
  537.   p[ItemOnNode-1].ulFilePageID = 0;
  538.   p[ItemOnNode-1].uiOffset     = 0;
  539.   k[ItemOnNode-1]            = NULL;
  540.   ItemOnNode--;
  541. }
  543. ///////////////////////////////////////////////////////////////////////////////////////////////
  544. // delete the key in the node, and automatic adjust the node
  545. void BPTreeNode::deleteKeyNotLeaf(pKey_Attr pPrimKey) {
  546.   int i;
  547.   for(i=0;i<ItemOnNode;i++)
  548.   {
  549.     if( compare(pPrimKey,k[i]) == 0 )
  550.       break;
  551.   }
  552.   deleteKeySpace(k[i]);  // delete the space of k[i]
  553.   // adjust the node
  554.   for(;i<ItemOnNode-1;i++)
  555.   {
  556.     k[i]   = k[i+1];
  557.     p[i+1] = p[i+2];
  558.   }
  559.   k[ItemOnNode-1]          = NULL;
  560.   p[ItemOnNode].ulFilePageID = 0;
  561.   p[ItemOnNode].uiOffset     = 0;
  562.   ItemOnNode--;
  563. }
  565. ///////////////////////////////////////////////////////////////////////////////////////////////
  566. // delete the space of the first key in the node
  567. void BPTreeNode::deleteFirstKey() {
  568.     pKey_Attr head,temp;
  569.     head = temp = k[0];
  570.     for(int j=0;KeyInfo[j]!=0;j++)
  571.     {
  572.       switch(KeyInfo[j])
  573.       {
  574.         case 'i' :  // int 
  575.                     head = head->next;
  576.                     delete temp;
  577.                     temp = head;
  578.                     break;
  579.         case 'f' :  // float
  580.                     head = head->next;
  581.                     delete temp;
  582.                     temp = head;
  583.                     break;
  584.         case 'c' :  // char
  585.                     delete  [] (head->value.pCharValue);
  586.                     head = head->next;
  587.                     delete temp;
  588.                     temp = head;
  589.                     while(isdigit(KeyInfo[++j])) ;  //skip digital number
  590.                     j--;
  591.                     break;
  592.       }
  593.     }
  594.     for(int i=0;i<ItemOnNode-1;i++)
  595.     {
  596.       p[i] = p[i+1];
  597.       k[i] = k[i+1];
  598.     }
  599.     p[ItemOnNode-1] = p[ItemOnNode];
  600.     p[ItemOnNode].ulFilePageID = 0;
  601.     p[ItemOnNode].uiOffset     = 0;
  602.     k[ItemOnNode - 1]        = NULL;
  603.     ItemOnNode--;
  604. }
  606. ///////////////////////////////////////////////////////////////////////////////////////////////
  607. // delete the space of the key
  608. void BPTreeNode::deleteKeySpace(pKey_Attr Key) {
  609.   pKey_Attr head,temp;
  610.   head = temp = Key;
  611.   for(int j=0;KeyInfo[j]!=0;j++)
  612.   {
  613.     switch(KeyInfo[j])
  614.     {
  615.       case 'i' :  // int 
  616.                   head = head->next;
  617.                   delete temp;
  618.                   temp = head;
  619.                   break;
  620.       case 'f' :  // float
  621.                   head = head->next;
  622.                   delete temp;
  623.                   temp = head;
  624.                   break;
  625.       case 'c' :  // char
  626.                   delete  [] (head->value.pCharValue);
  627.                   head = head->next;
  628.                   delete temp;
  629.                   temp = head;
  630.                   while(isdigit(KeyInfo[++j])) ;  //skip digital number
  631.                   j--;
  632.                   break;
  633.     }
  634.   }
  635. }
  637. ///////////////////////////////////////////////////////////////////////////////////////////////
  638. // create a key equal to Key1,and automatic open a new space 
  639. pKey_Attr BPTreeNode::createKey(pKey_Attr Key1) {
  640.   pKey_Attr Key2,temp;
  641.   for(int j=0; KeyInfo[j]!='';j++)
  642.   {
  643.     if(j == 0)    // the first node
  644.       Key2 = temp = new Key_Attr;
  645.     else
  646.     {
  647.       temp->next = new Key_Attr;
  648.       temp       = temp->next;
  649.     }
  650.     switch(KeyInfo[j])
  651.     {
  652.       case 'i'  :  // int value  
  653.                    temp->value.IntValue = Key1->value.IntValue;
  654.                    temp->next           = NULL;
  655.                    break;
  656.       case 'f'  :  // float value 
  657.                    temp->value.FloatValue = Key1->value.FloatValue;
  658.                    temp->next           = NULL;
  659.                    break;
  660.       case 'c'  :  // string
  661.                    int num = 0;
  662.                    for( j=j+1; isdigit(KeyInfo[j]); j++)
  663.                    {
  664.                      num = num * 10 + KeyInfo[j] - '0';
  665.                    }
  666.                    j--;        // move the index back
  667.                    num++;      // for '' which is the end of a string
  668.                    char* pCharValue = new char [num];
  669.                    char* str = Key1->value.pCharValue;
  670.                    strcpy(pCharValue,str);
  671.                    temp->value.pCharValue = pCharValue;
  672.                    temp->next             = NULL;
  673.                    break;                  
  674.     }
  675.     Key1 = Key1->next;  // move to the next node
  676.   }  //KeyInfo[i] = ''
  677.   return Key2;
  678. }
  680. ///////////////////////////////////////////////////////////////////////////////////////////////
  681. bool BPTreeNode::isNotEnoughPoints() {
  682.   int n = MaxItem + 1;  
  683.   if( 0 == IsLeaf )  // it isn't a leaf
  684.   {
  685.     int m;
  686.     if( !(n%2) )
  687.       m = n/2 ;  // n = NodeL.MaxItem + 1
  688.     else 
  689.       m = n/2 + 1;
  690.     if( (ItemOnNode + 1) < m)  // not enough points ,ItemOnNode+1 is the number of points
  691.       return true;
  692.     else 
  693.       return false;
  694.   }
  695.   else // it is a leaf
  696.   {
  697.     int m;
  698.     if( ! ((n-1)%2) )
  699.       m = (n-1)/2 ;  // n = NodeL.MaxItem + 1
  700.     else 
  701.       m = (n-1)/2 + 1;
  702.     if( ItemOnNode < m )  // not enough points
  703.       return true;
  704.     else 
  705.       return false;
  706.   }
  708. }
  709. ////////////////////////////////////////////////////////////////////////////////////////////////////
  711. /*=========================================================================
  712. =========                 definition for BPTree               =============
  713. =========================================================================*/
  715. ////////////////////////////////////////////////////////////////////////////////////////////////////
  716. //constructor
  717. BPTree::BPTree() {
  718. _F_FileAddr temp;
  719. temp.ulFilePageID = 0;
  720. temp.uiOffset     = 0;
  721. for(int i=0; i<DEPTH; i++)
  722. SearchPath[i] = temp;
  723. }
  725. //destructor
  727. BPTree::~BPTree() {
  729. }
  731. ////////////////////////////////////////////////////////////////////////////////////////////////////
  733. void BPTree::setPath() {
  734. char address[256];
  735. strcpy(address, CurLocation);
  736. strcat(address, CurRelationName);
  737. strcat(address, ".idx");
  738. _M_File test = Buffer[address]; 
  739. }
  741. ////////////////////////////////////////////////////////////////////////////////////////////////////
  743. void BPTree::create(char *KeyStr) {
  744. setPath();
  745. BPTree_Index idx;
  746. idx.createHead(KeyStr);
  747. idx.writeHeadToFile();
  749. BPTreeNode root;
  750. root.IsLeaf = 1;
  751. root.writeNodeToFile(idx.getRoot());
  752. }
  754. ////////////////////////////////////////////////////////////////////////////////////////////////////
  756. void BPTree::createNewRoot(_F_FileAddr p0, pKey_Attr pPrimKey, _F_FileAddr p1) {
  757. _F_FileAddr Newroot;
  758. Newroot = createNodeInFile();
  759. BPTree_Index idx;
  760. idx.readHeadFromFile();
  761. idx.IdxHead.root = Newroot;
  762. idx.writeHeadToFile();
  764. BPTreeNode Root;
  765. Root.IsLeaf = 0;
  766. Root.ItemOnNode = 1;
  767. Root.p[0] = p0;
  768. Root.p[1] = p1;
  769. Root.k[0] = pPrimKey;
  770. Root.writeNodeToFile(Newroot);
  771. }
  773. ////////////////////////////////////////////////////////////////////////////////////////////////////
  775. void BPTree::grantRoot(_F_FileAddr pfa) {
  776. BPTree_Index idx;
  777. idx.readHeadFromFile();
  778. idx.IdxHead.root = pfa;
  779. idx.writeHeadToFile();
  780. }
  782. ///////////////////////////////////////////////////////////////////////////////////////////////////
  784. void BPTree::deleteNodeInFile(_F_FileAddr pfa) {
  785. BPTree_Index idx;
  786. idx.readHeadFromFile();
  787. //make the first empty block point to the new delete block
  788. if(idx.IdxHead.FirstEmptyBlock.ulFilePageID == 0) {
  789. idx.IdxHead.FirstEmptyBlock = pfa;
  790. idx.IdxHead.LastEmptyBlock  = pfa;
  791. }
  792. else {
  793.     // make the last empty block point to the new delete block
  794.     BPTreeNode NextNode;
  795. NextNode.readNodeFromFile(idx.IdxHead.LastEmptyBlock);
  796.     NextNode.Next_Empty_Block = pfa;
  797.     NextNode.writeNodeToFile(idx.IdxHead.LastEmptyBlock);
  798.     // change the index head 
  799.     idx.IdxHead.LastEmptyBlock = pfa;
  800. }
  801. idx.writeHeadToFile();
  802. }
  804. ///////////////////////////////////////////////////////////////////////////////////////////////////
  805. //--
  806. bool BPTree::search(pKey_Attr pPrimKey, pKey_Location pKeyLoca) {
  807. setPath();
  808. BPTree_Index idx;
  809. idx.readHeadFromFile();
  810. _F_FileAddr pfa = idx.getRoot();
  812. BPTreeNode Node;
  813. for(int level=0; level<DEPTH; level++) {
  814. Node.readNodeFromFile(pfa);
  815. SearchPath[level] = pfa;
  816. //not leaf
  817. if(Node.IsLeaf == 0) {
  818. for(int i=0; i<=Node.ItemOnNode; i++) {
  819. if(i == Node.ItemOnNode) {
  820. pfa = Node.p[i];
  821. break;
  822. }
  823. else if(Node.compare(pPrimKey, Node.k[i]) < 0) {
  824. pfa = Node.p[i];
  825. break;
  826. }
  827. else if(Node.compare(pPrimKey,Node.k[i]) >= 0)
  828. continue;
  829. }
  830. }
  831. else {
  832. //is leaf
  833. for(int j=0; j<=Node.ItemOnNode; j++) {
  834. if(j == Node.ItemOnNode) {
  835. pKeyLoca->ptr = pfa;
  836. pKeyLoca->offset = Node.MaxItem;
  837. return false;
  838. }
  839. else if(Node.compare(pPrimKey, Node.k[j]) == 0) {
  840. pKeyLoca->ptr = pfa;
  841. pKeyLoca->offset = j;
  842. return true;
  843. }
  844. else if( Node.compare(pPrimKey,Node.k[j]) > 0 )  // pPrimKey > k[i]
  845. continue;
  846. else {
  847. pKeyLoca->ptr    = pfa;
  848. pKeyLoca->offset = j;
  849. return false;
  850. }
  851. }
  852. }
  853. }
  854. throw 1028;
  855. }
  857. ///////////////////////////////////////////////////////////////////////////////////////////////////
  858. //--
  859. bool BPTree::isRoot(_F_FileAddr pfa) {
  860. return SearchPath[0] == pfa;
  861. }
  863. ///////////////////////////////////////////////////////////////////////////////////////////////////
  864. //--
  865. bool BPTree::isEmpty() {
  866. Key_Location KeyLoca;
  867. // cout<<"begin isEmpty()"<<endl;//=======//
  868. KeyLoca = getStart();
  869. BPTreeNode FirstNode;
  870. FirstNode.readNodeFromFile(KeyLoca.ptr);
  871. // cout<<"end isEmpty()"<<endl;  //=====//
  872. if(FirstNode.ItemOnNode == 0)
  873. return true;
  874. return false;
  875. }
  877. ///////////////////////////////////////////////////////////////////////////////////////////////////
  878. //--
  879. Key_Location BPTree::moveToNextKey(Key_Location KeyLoca) {
  880. Key_Location temp;
  881. BPTreeNode node; 
  882. node.readNodeFromFile(KeyLoca.ptr);
  884. if( node.MaxItem == KeyLoca.offset ) {
  885. if(node.p[node.MaxItem].ulFilePageID == 0)
  886. temp.ptr.ulFilePageID = 0;
  887. else {
  888. // get the address of the first key in the next node 
  889. BPTreeNode NextNode;
  890. NextNode.readNodeFromFile(node.p[node.MaxItem]);
  891. temp.ptr = node.p[node.MaxItem];
  892. temp.offset = 0;
  893. }
  894. return temp;
  895. }
  897. int i = KeyLoca.offset + 1;
  898. // the next key is empty or full
  899. if( 0 == node.p[i].ulFilePageID || node.MaxItem == i) {
  900. i = node.MaxItem;  // the last p[MaxItem]
  901. if( 0 == node.p[i].ulFilePageID ) 
  902. temp.ptr.ulFilePageID = 0;
  903. else {
  904. BPTreeNode NextNode;
  905. NextNode.readNodeFromFile(node.p[i]);
  906. temp.ptr = node.p[i];
  907. temp.offset = 0;
  908. }
  909. }
  910. else {
  911. // the address of the next key in the current node 
  912. temp.ptr = KeyLoca.ptr;
  913. temp.offset = KeyLoca.offset + 1;
  914. }
  915. return temp;
  916. }
  918. ///////////////////////////////////////////////////////////////////////////////////////////////////
  919. //this method returns the address of the first key in the leftest leaf node
  920. //--
  921. Key_Location BPTree::getStart() {
  922. BPTree_Index idx;
  923. idx.readHeadFromFile();
  924. _F_FileAddr ptr = idx.getRoot();
  925.   
  926.     for( ; ; ) {
  927. BPTreeNode Node;
  928. Node.readNodeFromFile(ptr);
  929. if( 1 == Node.IsLeaf ) {
  930. Key_Location temp;
  931. temp.ptr = ptr;
  932. temp.offset = 0;
  933. return temp;
  934. }
  935. else
  936. ptr = Node.p[0];
  937. }
  938. }
  940. ///////////////////////////////////////////////////////////////////////////////////////////////////
  941. //--
  942. _F_FileAddr BPTree::getParent(_F_FileAddr ptr) {
  943. for(int i=0; SearchPath[i].ulFilePageID != 0; i++) {
  944. if(SearchPath[i] == ptr)
  945. return SearchPath[i-1];  
  946. }
  947. throw 1022;
  948. }
  950. ///////////////////////////////////////////////////////////////////////////////////////////////////
  951. //this method returns the address specified by Key_Location
  952. //--
  953. _F_FileAddr BPTree::getCurRecAddr(Key_Location KeyLoca) {
  954. BPTreeNode node;
  955. node.readNodeFromFile(KeyLoca.ptr);
  956. return node.p[KeyLoca.offset];
  957. }
  959. ///////////////////////////////////////////////////////////////////////////////////////////////////
  960. //--
  961. _F_FileAddr BPTree::createNodeInFile() {
  962. BPTree_Index idx;
  963. idx.readHeadFromFile();
  964. //the index file has no empty block
  965. if( 0 == idx.IdxHead.FirstEmptyBlock.ulFilePageID ) {
  966. // firstly,we should check whether the block overflow the current page
  967. // If so,use the next page 
  968. void* CheckOverflow = (void*) new char[BTreeNodeSize];
  969. _F_FileAddr Next = MemWrite(CheckOverflow, BTreeNodeSize, &idx.IdxHead.FirstNewBlock);
  970. _F_FileAddr temp = idx.IdxHead.FirstNewBlock;
  971. idx.IdxHead.FirstNewBlock = Next;
  972. idx.writeHeadToFile();
  973. return temp;
  974. }
  975. else {
  976. int flag = 0;  
  977. if(idx.IdxHead.FirstEmptyBlock ==  idx.IdxHead.LastEmptyBlock)
  978. flag = 1;
  979. _F_FileAddr temp = idx.IdxHead.FirstEmptyBlock;
  980. if( 1 == flag) { 
  981. //there is just one empty block
  982. idx.IdxHead.FirstEmptyBlock.ulFilePageID = 0;
  983. idx.IdxHead.FirstEmptyBlock.uiOffset     = 0;
  984. idx.IdxHead.LastEmptyBlock.ulFilePageID  = 0;
  985. idx.IdxHead.LastEmptyBlock.uiOffset      = 0;
  986. }
  987. else {
  988. // change FisrtEmptyBlock point to the next block
  989. BPTreeNode NextNode;
  990. NextNode.readNodeFromFile(temp);
  991. idx.IdxHead.FirstEmptyBlock = NextNode.Next_Empty_Block;
  992. }
  993. idx.writeHeadToFile();
  994. return temp;
  995. }
  996. }
  998. ///////////////////////////////////////////////////////////////////////////////////////////////////
  999. //this method returns the address of the last key in the rightest node
  1000. //--
  1001. Key_Location BPTree::getEnd() {
  1002. BPTree_Index idx;
  1003. idx.readHeadFromFile();
  1004. _F_FileAddr ptr = idx.getRoot();
  1006. for( ; ; ) {
  1007. BPTreeNode Node;
  1008. Node.readNodeFromFile(ptr);
  1009. if( 1 == Node.IsLeaf ) {
  1010. Key_Location temp;
  1011. temp.ptr = ptr;
  1012. temp.offset = Node.ItemOnNode - 1;
  1013. return temp;  // return the first address of the first Key in the first node
  1014. }
  1015. else
  1016. ptr = Node.p[Node.ItemOnNode];
  1017. }
  1018. }
  1020. ///////////////////////////////////////////////////////////////////////////////////////////////////
  1021. //--
  1022. void BPTree::insert(pKey_Attr pPrimKey, _F_FileAddr pRec) {
  1023. setPath();
  1024. Key_Location KeyLoca;
  1025. if(search(pPrimKey, &KeyLoca))
  1026. throw 1024;
  1027. else 
  1028. insert_entry(KeyLoca.ptr, pPrimKey, pRec);
  1029. }
  1031. ///////////////////////////////////////////////////////////////////////////////////////////////////
  1032. //--
  1033. void BPTree::insert_entry(_F_FileAddr L, pKey_Attr pPrimKey, _F_FileAddr pRec) {
  1034. BPTreeNode NodeL;
  1035. NodeL.readNodeFromFile(L);
  1036. //if L has less than n-1 key values
  1037. if(NodeL.ItemOnNode < NodeL.MaxItem) {
  1038. if(NodeL.IsLeaf ==1)
  1039. NodeL.insertKeyInLeaf(pRec, pPrimKey);
  1040. else
  1041. NodeL.insertKeyNotLeaf(pPrimKey, pRec);
  1042. }
  1043. else {
  1044. //create a new node
  1045. _F_FileAddr L_ = createNodeInFile();
  1046. BPTreeNode NodeL_;
  1047. pKey_Attr pPrimKey_;
  1048. int n = NodeL.MaxItem + 1;
  1050. if(NodeL.IsLeaf ==1) {
  1051. NodeL_.IsLeaf = 1;
  1052. int m;
  1053. if( !(n%2) )
  1054. m = n/2 ;
  1055. else 
  1056. m = n/2 + 1;
  1057. //p[0]k[0]...k[m-1]p[m] | k[m]...
  1058. // pPrimKey < k[m-1]
  1059. if( NodeL.compare(NodeL.k[m-1], pPrimKey) > 0) { 
  1060. m--;                                  
  1061. pPrimKey_ = NodeL.createKey(NodeL.k[m]);
  1062. }
  1063. // k[m] > pPrimKey >= k[m-1]
  1064. else if( (m == n - 1) || ( NodeL.compare(NodeL.k[m], pPrimKey) > 0 ) ) 
  1065. pPrimKey_ = NodeL.createKey(pPrimKey);
  1066. else
  1067. // pPrimKey > k[m]
  1068. pPrimKey_ = NodeL.createKey(NodeL.k[m]);
  1069. //copy p[m]....to L_
  1070. for(int i=m; i<NodeL.MaxItem; i++) {
  1071. NodeL_.p[i-m] = NodeL.p[i];
  1072. NodeL_.k[i-m] = NodeL.k[i];
  1073. //erase
  1074. NodeL.k[i] = NULL;
  1075. NodeL.p[i].ulFilePageID = 0;
  1076. NodeL.p[i].uiOffset     = 0;
  1077. NodeL_.ItemOnNode++;
  1078. NodeL.ItemOnNode--;
  1079. }
  1080. if(NodeL.compare(pPrimKey, pPrimKey_) < 0)
  1081. NodeL.insertKeyInLeaf(pRec,pPrimKey);
  1082. else
  1083. NodeL_.insertKeyInLeaf(pRec,pPrimKey);
  1084. }
  1085. else { //NodeL is not a leaf
  1086. NodeL_.IsLeaf = 0;
  1087. int m;
  1088. if( !(n%2) )
  1089. m = n/2 ;
  1090. else 
  1091. m = n/2 + 1;
  1092. m = NodeL.MaxItem - m;
  1093. //p[0],k[0]....k[m]p[m+1] | k[m+1]...
  1094. //pPrimKey > k[m+1]
  1095. if( NodeL.compare(pPrimKey, NodeL.k[m+1]) > 0 ) {
  1096. m++;
  1097. pPrimKey_ = NodeL.createKey(NodeL.k[m]);
  1098. }
  1099. // k[m] < pPrimKey <= k[m+1]
  1100. else if( NodeL.compare(pPrimKey, NodeL.k[m]) > 0 ) {
  1101. m++;
  1102. pPrimKey_ = NodeL.createKey(pPrimKey);
  1103. }
  1104. // pPrimKey <= k[m]
  1105. else {
  1106. pPrimKey_ = NodeL.createKey(NodeL.k[m]);
  1107. }
  1108. // move and delete
  1109. NodeL_.p[0].ulFilePageID = 0;
  1110. NodeL_.p[0].uiOffset     = 0;  
  1111. NodeL_.k[0] = NodeL.k[m];
  1112. NodeL.k[m] = NULL;
  1113. NodeL_.ItemOnNode++;
  1114. NodeL.ItemOnNode--;
  1115. for(int i=m+1; i<NodeL.MaxItem; i++) {
  1116. NodeL_.p[i-m] = NodeL.p[i];
  1117. NodeL_.k[i-m] = NodeL.k[i];
  1118. //erase
  1119. NodeL.k[i] = NULL;
  1120. NodeL.p[i].ulFilePageID = 0;
  1121. NodeL.p[i].uiOffset     = 0;
  1122. NodeL_.ItemOnNode++;
  1123. NodeL.ItemOnNode--;
  1124. }
  1125. NodeL_.p[i-m] = NodeL.p[i];
  1126. NodeL.p[i].ulFilePageID = 0;
  1127. NodeL.p[i].uiOffset     = 0;
  1128. if( NodeL.compare(pPrimKey, pPrimKey_) < 0 )
  1129. NodeL.insertKeyNotLeaf(pPrimKey, pRec);
  1130. else 
  1131. NodeL_.insertKeyNotLeaf(pPrimKey,pRec);
  1132. NodeL_.deleteFirstKey();
  1133. }
  1134. if( !isRoot(L) )
  1135. insert_entry(getParent(L), pPrimKey_, L_);
  1136. else
  1137. createNewRoot(L, pPrimKey_, L_);  
  1138. if(NodeL.IsLeaf == 1) {
  1139. NodeL_.p[NodeL.MaxItem] = NodeL.p[NodeL.MaxItem];
  1140. NodeL.p[NodeL.MaxItem]  = L_;
  1141. }
  1142. NodeL_.writeNodeToFile(L_);
  1143. }
  1144. NodeL.writeNodeToFile(L);
  1145. }
  1147. //////////////////////////////////////////////////////////////////////////////////////////////////////////
  1149. bool BPTree::canCoalesce(BPTreeNode* pNode, BPTreeNode* pNode_) {
  1150. if(pNode->IsLeaf == 1)
  1151. return (pNode->ItemOnNode + pNode_->ItemOnNode <= pNode->MaxItem);
  1152. else
  1153. return (pNode->ItemOnNode + pNode_->ItemOnNode < pNode->MaxItem);   
  1154. }
  1156. //////////////////////////////////////////////////////////////////////////////////////////////////////////
  1159. void BPTree::coalesce(BPTreeNode* pNodeL, BPTreeNode* pNodeL_, pKey_Attr pPrimKey_, bool IsLLeftOfL_) {
  1160. if( 0 == pNodeL->IsLeaf ) {
  1161. if(IsLLeftOfL_) {
  1162. //move right
  1163. int j = pNodeL->ItemOnNode + 1;
  1164. pNodeL_->p[pNodeL_->ItemOnNode + j] = pNodeL_->p[pNodeL_->ItemOnNode];
  1165. for(int i=pNodeL_->ItemOnNode-1; i>=0; i--) {
  1166. pNodeL_->k[i + j] = pNodeL_->k[i];
  1167. pNodeL_->p[i + j] = pNodeL_->p[i];
  1168. }
  1169. //assign V' to the pNodeL_
  1170. pNodeL_->k[j-1] = pPrimKey_;
  1171. pNodeL_->p[j-1] = pNodeL->p[pNodeL->ItemOnNode];
  1172. // move all elements in pNodeL to pNodeL_
  1173. for(i=0; i<pNodeL->ItemOnNode; i++) {
  1174. pNodeL_->p[i] = pNodeL->p[i];
  1175. pNodeL_->k[i] = pNodeL->k[i];
  1176. }
  1177. // set ItemOnNode in pNodeL_
  1178. pNodeL_->ItemOnNode = pNodeL_->ItemOnNode + pNodeL->ItemOnNode + 1;
  1179. pNodeL->initialize();
  1180. }
  1181. else { //L is right of L_
  1182. int j = pNodeL_->ItemOnNode + 1;
  1183. pNodeL_->k[pNodeL_->ItemOnNode] = pPrimKey_; 
  1184. for(int i=0;i<pNodeL->ItemOnNode;i++) {
  1185. pNodeL_->p[i+j] = pNodeL->p[i];
  1186. pNodeL_->k[i+j] = pNodeL->k[i];
  1187. }
  1188. pNodeL_->p[i+j] = pNodeL->p[i];
  1189. pNodeL_->ItemOnNode = pNodeL_->ItemOnNode + pNodeL->ItemOnNode + 1;
  1190. pNodeL->initialize();
  1191. }
  1192. }
  1193. else { // (pNodeL->IsLeaf == 1)
  1194. if(IsLLeftOfL_) {
  1195. int j = pNodeL->ItemOnNode;
  1196. for(int i=0; i<pNodeL_->ItemOnNode; i++) {
  1197. pNodeL->p[i+j] = pNodeL_->p[i];
  1198. pNodeL->k[i+j] = pNodeL_->k[i];
  1199. }
  1200. pNodeL->ItemOnNode += pNodeL_->ItemOnNode;
  1201. pNodeL->p[pNodeL->MaxItem] = pNodeL_->p[pNodeL_->MaxItem];
  1202. pNodeL_->initialize();
  1203. }
  1204. else { // L is right of L_
  1205. int j = pNodeL_->ItemOnNode;
  1206. for(int i=0; i<pNodeL->ItemOnNode; i++) {
  1207. pNodeL_->p[i+j] = pNodeL->p[i];
  1208. pNodeL_->k[i+j] = pNodeL->k[i];
  1209. }
  1210. pNodeL_->ItemOnNode += pNodeL->ItemOnNode;
  1211. pNodeL_->p[pNodeL_->MaxItem] = pNodeL->p[pNodeL->MaxItem];
  1212. pNodeL->initialize();
  1213. }
  1214. }
  1215. }
  1217. ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  1218. //this method swaps the pointers to node L and L_
  1220. void BPTree::swapVariables(_F_FileAddr L, _F_FileAddr L_) {
  1221. BPTreeNode ParentNode;
  1222. ParentNode.readNodeFromFile(getParent(L));
  1223. int m,n;
  1224. // find the indexes of L and L_ 
  1225. for(int i=0; i <= ParentNode.ItemOnNode; i++) {
  1226. if( ParentNode.p[i] == L )
  1227. m = i;
  1228. if( ParentNode.p[i] == L_ )
  1229. n = i;
  1230. }
  1231. // swap
  1232. _F_FileAddr temp;
  1233. temp = ParentNode.p[m];
  1234. ParentNode.p[m] = ParentNode.p[n];
  1235. ParentNode.p[n] = temp;
  1236. ParentNode.writeNodeToFile(getParent(L));
  1237. }
  1239. ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  1240. //this method makes pL_ and ppPrimKey points the infomation that is a neighbour of L
  1241. // and pIsLLeftOnL_ indicate whether L is left neighbour of L_ or not
  1243. void BPTree::setNb(_F_FileAddr L, _F_FileAddr* pL_, pKey_Attr* ppPrimKey_, bool* pIsLLeftOfL_) {
  1244. BPTreeNode ParentNode;
  1245. ParentNode.readNodeFromFile(getParent(L));
  1246. for(int i=0; i<=ParentNode.ItemOnNode; i++) {
  1247. if( ParentNode.p[i] == L )
  1248. break;
  1249. }
  1250. if( 0 == i ) { // L is the leftest son of the parent node
  1251. (*pL_)          = ParentNode.p[1];
  1252. (*ppPrimKey_)   = ParentNode.createKey(ParentNode.k[0]);
  1253. (*pIsLLeftOfL_) = true;  // L is on the left of L_
  1254. }
  1255. else {
  1256. (*pL_)          = ParentNode.p[i-1];
  1257. (*ppPrimKey_)   = ParentNode.createKey(ParentNode.k[i-1]);
  1258. (*pIsLLeftOfL_) = false;
  1259. }
  1260. }
  1262. ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  1263. //this method replaces the key equal to Key_ with Key in the node pointed by ptr  
  1264. //--
  1265. void BPTree::replaceKey(_F_FileAddr ptr, pKey_Attr Key_, pKey_Attr Key) {
  1266. BPTreeNode Node;
  1267. Node.readNodeFromFile(ptr);
  1268. for(int i=0; i<Node.ItemOnNode; i++) {
  1269. if( 0 == Node.compare(Node.k[i], Key_) )
  1270. break;
  1271. }
  1272. Node.deleteKeySpace(Node.k[i]);
  1273. Node.k[i] = Key;
  1274. Node.writeNodeToFile(ptr);
  1275. }
  1277. ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  1279. void BPTree::reDistribute(BPTreeNode* pNodeL, BPTreeNode* pNodeL_, pKey_Attr pPrimKey_, 
  1280.   bool IsLLeftOfL_, _F_FileAddr L) {
  1281. int m;
  1282. if( !IsLLeftOfL_ ) {
  1283. if( !pNodeL->IsLeaf ) {
  1284. m = pNodeL_->ItemOnNode;
  1285. //  move all k[i] and p[i] in L to right by one
  1286. pNodeL->p[pNodeL->ItemOnNode+1] = pNodeL->p[pNodeL->ItemOnNode];
  1287. for(int i=pNodeL->ItemOnNode-1; i>=0; i--) {
  1288. pNodeL->k[i+1] = pNodeL->k[i];
  1289. pNodeL->p[i+1] = pNodeL->p[i];
  1290. }
  1291. pNodeL->k[0] = pPrimKey_;
  1292. pNodeL->p[0] = pNodeL_->p[m];
  1293. pNodeL->ItemOnNode++;
  1294. //replace K_ in parent of L by k[m-1]
  1295. replaceKey(getParent(L), pPrimKey_, pNodeL_->k[m-1]);
  1296. //remove k[m-1] and p[m] from L_
  1297. pNodeL_->k[m-1] = NULL;
  1298. pNodeL_->p[m].ulFilePageID = 0;
  1299. pNodeL_->p[m].uiOffset     = 0;
  1300. pNodeL_->ItemOnNode--;
  1301. }
  1302. else { //(pNodeL->IsLeaf == 1)
  1303. m = pNodeL_->ItemOnNode - 1;
  1304. //  move all k[i] and p[i] in L to right by one
  1305. for(int i=pNodeL->ItemOnNode-1; i>=0; i--) {
  1306. pNodeL->k[i+1] = pNodeL->k[i];
  1307. pNodeL->p[i+1] = pNodeL->p[i];
  1308. }
  1309. pNodeL->k[0] = pNodeL_->k[m];
  1310. pNodeL->p[0] = pNodeL_->p[m];
  1311. pNodeL->ItemOnNode++;
  1312. //replace K_ in parent of L by k[m]
  1313. pKey_Attr temp = pNodeL_->createKey(pNodeL_->k[m]);
  1314. replaceKey(getParent(L), pPrimKey_, temp);
  1315. pNodeL->deleteKeySpace(pPrimKey_);
  1316. //remove p[m] and k[m] from L_ 
  1317. pNodeL_->k[m] = NULL;
  1318. pNodeL_->p[m].ulFilePageID = 0;
  1319. pNodeL_->p[m].uiOffset     = 0;
  1320. pNodeL_->ItemOnNode--;
  1321. }
  1322. }
  1323. else { //(IsLLeftOfL_)
  1324. if( !pNodeL->IsLeaf ) {
  1325. pNodeL->k[pNodeL->ItemOnNode] = pPrimKey_;
  1326. pNodeL->p[pNodeL->ItemOnNode + 1] = pNodeL_->p[0];
  1327. pNodeL->ItemOnNode++;
  1328. replaceKey(getParent(L), pPrimKey_, pNodeL_->k[0]);
  1329. // move pNodeL_ to the left by one
  1330. for(int i=1; i<pNodeL_->ItemOnNode; i++) {
  1331. pNodeL_->k[i-1] = pNodeL_->k[i];
  1332. pNodeL_->p[i-1] = pNodeL_->p[i];
  1333. }
  1334. pNodeL_->p[i-1] = pNodeL_->p[i];
  1336. pNodeL_->k[pNodeL_->ItemOnNode-1] = NULL;
  1337. pNodeL_->p[pNodeL_->ItemOnNode].ulFilePageID = 0;
  1338. pNodeL_->p[pNodeL_->ItemOnNode].uiOffset     = 0;
  1339. pNodeL_->ItemOnNode--;
  1340. }
  1341. else { //(pNodeL->IsLeaf)
  1342. pNodeL->k[pNodeL->ItemOnNode] = pNodeL_->k[0];
  1343. pNodeL->p[pNodeL->ItemOnNode] = pNodeL_->p[0];
  1344. pNodeL->ItemOnNode++;
  1345. for(int i=1; i<pNodeL_->ItemOnNode; i++) {
  1346. pNodeL_->k[i-1] = pNodeL_->k[i];
  1347. pNodeL_->p[i-1] = pNodeL_->p[i];
  1348. }
  1349. pNodeL_->k[pNodeL_->ItemOnNode-1] = NULL;
  1350. pNodeL_->p[pNodeL_->ItemOnNode-1].ulFilePageID = 0;
  1351. pNodeL_->p[pNodeL_->ItemOnNode-1].uiOffset     = 0;
  1352. pNodeL_->ItemOnNode--;
  1353. pKey_Attr temp = pNodeL_->createKey(pNodeL_->k[0]); 
  1354. replaceKey(getParent(L), pPrimKey_, temp);
  1355. pNodeL->deleteKeySpace(pPrimKey_);
  1356. }
  1357. }
  1358. }
  1360. ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  1362. void BPTree::myDelete(pKey_Attr pPrimKey, _F_FileAddr& pRec) {
  1363. setPath();
  1364. Key_Location KeyLoca;
  1365. if(search(pPrimKey, &KeyLoca)) {
  1366. pRec = getCurRecAddr(KeyLoca);
  1367. delete_entry(KeyLoca.ptr, pPrimKey, pRec);    
  1368. }
  1369. else
  1370. throw 1023;
  1371. }
  1373. ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  1375. void BPTree::delete_entry(_F_FileAddr L, pKey_Attr pPrimKey, _F_FileAddr pRec) {
  1376. BPTreeNode NodeL;
  1377. NodeL.readNodeFromFile(L);
  1378. // delete the (V,P) entry
  1379. if( 1 == NodeL.IsLeaf )
  1380. NodeL.deleteKeyInLeaf(pPrimKey);
  1381. else 
  1382. NodeL.deleteKeyNotLeaf(pPrimKey);
  1383. // L is root and has only one son and not a leaf
  1384. if( isRoot(L) && ( 0 == NodeL.ItemOnNode ) && (0 == NodeL.IsLeaf) )  {
  1385. grantRoot(NodeL.p[0]); // grant root to the son
  1386. deleteNodeInFile(L);   // delete node 
  1387. }
  1388. else 
  1389. if( !isRoot(L) && NodeL.isNotEnoughPoints() )  {// isn't root and not enough points
  1390. //set L_ neighbour of L
  1391. bool IsLLeftOfL_;
  1392. _F_FileAddr L_;
  1393. pKey_Attr pPrimKey_;
  1394. setNb(L, &L_, &pPrimKey_, &IsLLeftOfL_);
  1395.     
  1396. BPTreeNode NodeL_;
  1397. NodeL_.readNodeFromFile(L_);
  1398. if( canCoalesce(&NodeL, &NodeL_)) {
  1399. if(IsLLeftOfL_) 
  1400. swapVariables(L,L_); 
  1401. coalesce(&NodeL, &NodeL_, pPrimKey_, IsLLeftOfL_);
  1402. if( NodeL.IsLeaf && IsLLeftOfL_ ) // differe from book 
  1403. swapVariables(L,L_);       
  1405. delete_entry(getParent(L), pPrimKey_, L);
  1406. if( NodeL.IsLeaf && IsLLeftOfL_ )  // L is a leaf and L < L_. Different from the book
  1407. deleteNodeInFile(L_);  // delete the node pointed by L_
  1408. else
  1409. deleteNodeInFile(L);   // delete the node pointed by L
  1410. }
  1411. else 
  1412.   reDistribute(&NodeL, &NodeL_, pPrimKey_, IsLLeftOfL_, L);
  1414. NodeL_.writeNodeToFile(L_);
  1415. }
  1416. NodeL.writeNodeToFile(L);  // if though the node is delete
  1417. }
  1419. ///////////////////////////////////////////////////////////////////////////////////////////////////////////