ndx.cpp

一个通讯管理机的源代码。比较好用。推荐

      SaveNodeChain = NodeChain;
      NodeChain = NULL;
      SaveCurNode = CurNode;
      GetLastKey( CurNode->NodeNo, 0 );
      memcpy( KeyBuf, GetKeyData( CurNode->CurKeyNo, CurNode ),HeadNode.KeyLen);
      ReleaseNodeMemory( NodeChain );
      NodeChain = SaveNodeChain;
      CurNode = SaveCurNode;
      PutKeyData( n1->CurKeyNo, n1 );
      PutLeftNodeNo( n1->CurKeyNo + 1, n1, t );
   }
   else if( n1->CurKeyNo + 1 == HeadNode.KeysPerNode )
   {
      SaveNodeChain = NodeChain;
      NodeChain = NULL;
      SaveCurNode = CurNode;
      GetLastKey( t, 0 );
      memcpy( KeyBuf,GetKeyData(CurNode->CurKeyNo,CurNode), HeadNode.KeyLen ); 
      PutKeyData( 0, n2 );
      PutLeftNodeNo( 0, n2, t ); 
      PutLeftNodeNo( 1, n2, GetLeftNodeNo( n1->Leaf.NoOfKeysThisNode, n1 ));
      ReleaseNodeMemory( NodeChain );
      NodeChain = SaveNodeChain;
      CurNode = SaveCurNode;
      n2->Leaf.NoOfKeysThisNode = 1;
      n1->Leaf.NoOfKeysThisNode--;
   }
   else /* pos = HeadNode.KeysPerNode */
   {
      SaveNodeChain = NodeChain;
      NodeChain = NULL;
      SaveCurNode = CurNode;
      GetLastKey( CurNode->NodeNo, 0 );
      memcpy( KeyBuf, GetKeyData( CurNode->CurKeyNo, CurNode ), HeadNode.KeyLen );
      ReleaseNodeMemory( NodeChain );
      NodeChain = SaveNodeChain;
      CurNode = SaveCurNode;

      PutKeyData( 0, n2 );
      PutLeftNodeNo( 0, n2, CurNode->NodeNo );
      PutLeftNodeNo( 1, n2, t );
      n2->Leaf.NoOfKeysThisNode = 1;
      n1->Leaf.NoOfKeysThisNode--;
   }
   n2->NodeNo = HeadNode.TotalNodes++; 
   if((rc = PutLeafNode( n1->NodeNo,n1 )) != 0) return rc;
   if((rc = PutLeafNode( n2->NodeNo,n2 )) != 0) return rc;
   return 0;
}
/************************************************************************/
//! Short description
/*!
  \param RecBufSw
  \param KeyBufSw
*/
xbShort xbNdx::CreateKey( xbShort RecBufSw, xbShort KeyBufSw )
{ 
   /* RecBufSw   0   Use RecBuf    */
   /*            1   Use RecBuf2   */
   /* KeyBufSw   0   Use KeyBuf    */
   /*            1   Use KeyBuf2   */

   xbShort rc;
   xbExpNode * TempNode;

   if(( rc = dbf->xbase->ProcessExpression( ExpressionTree, RecBufSw )) != XB_NO_ERROR )
      return rc;
   TempNode = (xbExpNode *) dbf->xbase->Pop();
   if( !TempNode )
       xb_error(XB_INVALID_KEY);

   if( KeyBufSw )
   {
      if( HeadNode.KeyType == 1 )    /* numeric key   */
         dbf->xbase->PutDouble( KeyBuf2, TempNode->DoubResult );
      else                           /* character key */
      {
         memset( KeyBuf2, 0x00, HeadNode.KeyLen + 1 );
         memcpy( KeyBuf2, TempNode->StringResult, TempNode->DataLen );
      }
   }
   else
   {
      if( HeadNode.KeyType == 1 )    /* numeric key   */
         dbf->xbase->PutDouble( KeyBuf, TempNode->DoubResult );
      else                           /* character key */
      {
         memset( KeyBuf, 0x00, HeadNode.KeyLen + 1 );
         memcpy( KeyBuf, TempNode->StringResult.c_str(), TempNode->DataLen );
      }
   }
//   if( !TempNode->InTree ) dbf->xbase->FreeExpNode( TempNode );
   if( !TempNode->InTree ) delete TempNode;
   return 0;
}
/************************************************************************/
//! Short description
/*!
  \param key
*/
xbShort  
xbNdx::GetCurrentKey(char *key)
{
  CreateKey(0, 0);
  if(HeadNode.KeyType == 1)
    memcpy(key, KeyBuf, 8);
  else
    memcpy(key, KeyBuf, HeadNode.KeyLen + 1);
    
  return 0;
}
/************************************************************************/
//! Short description
/*!
  \param DbfRec
*/
xbShort xbNdx::AddKey( xbLong DbfRec )
{
 /* This routine assumes KeyBuf contains the contents of the index to key */
   
   char *p;
   xbShort i,rc;
   xbNdxNodeLink * TempNode;   
   xbNdxNodeLink * Tparent;
   xbLong TempNodeNo = 0L;          /* new, unattached leaf node no */
   xbNdxNodeLink * SaveNodeChain;
   xbNdxNodeLink * SaveCurNode;

   /* find node key belongs in */
   rc = FindKey( KeyBuf, HeadNode.KeyLen, 0 );
   if( rc == XB_FOUND && HeadNode.Unique )
     xb_error(XB_KEY_NOT_UNIQUE);

  if( CurNode->Leaf.NoOfKeysThisNode > 0 && rc == XB_FOUND )
  {
    rc = 0;
    while( rc == 0 )
    {
      if(( p = GetKeyData( CurNode->CurKeyNo, CurNode )) == NULL )  
        rc = -1;
      else
      {
        rc = CompareKey( KeyBuf, p, HeadNode.KeyLen );
        if( rc == 0 && DbfRec >= GetDbfNo( CurNode->CurKeyNo, CurNode ))
        {
#ifdef HAVE_EXCEPTIONS
        try {
#endif
          if((rc = GetNextKey(0)) == XB_EOF) {
            if((rc = GetLastKey(0, 0)) != XB_NO_ERROR)
              return rc;
            CurNode->CurKeyNo++;
          }
#ifdef HAVE_EXCEPTIONS
          } catch (xbEoFException &) {
            GetLastKey(0, 0);
            CurNode->CurKeyNo++;
          }
#endif
        }
        else 
          rc = -1;
      }
    }
  }

   /* update header node */
   HeadNode.NoOfKeys++;
   /************************************************/
   /* section A - if room in node, add key to node */
   /************************************************/

   if( CurNode->Leaf.NoOfKeysThisNode < HeadNode.KeysPerNode )
   {
      if(( rc = PutKeyInNode( CurNode,CurNode->CurKeyNo,DbfRec,0L,1)) != 0)
      {
         return rc;
      }
      if(( rc = PutHeadNode( &HeadNode, indexfp, 1 )) != 0)
      {
         return rc;
      }
      return XB_NO_ERROR;
   }   

   /***********************************************************************/
   /* section B - split leaf node if full and put key in correct position */
   /***********************************************************************/

   TempNode = GetNodeMemory();
   TempNode->NodeNo = HeadNode.TotalNodes++;

   rc = SplitLeafNode( CurNode, TempNode, CurNode->CurKeyNo, DbfRec );
   if( rc ) 
   {
      return rc;
   }

   TempNodeNo = TempNode->NodeNo;
   ReleaseNodeMemory( TempNode );

   /*****************************************************/
   /* section C go up tree splitting nodes as necessary */
   /*****************************************************/
   Tparent = CurNode->PrevNode;

   while( Tparent && 
          Tparent->Leaf.NoOfKeysThisNode >= HeadNode.KeysPerNode )
   {
      TempNode = GetNodeMemory();
      if( !TempNode ) {
         xb_memory_error;
      }

      rc = SplitINode( Tparent, TempNode, TempNodeNo );
      if( rc ) return rc;

      TempNodeNo = TempNode->NodeNo;
      ReleaseNodeMemory( TempNode );
      ReleaseNodeMemory( CurNode );
      CurNode = Tparent;
      CurNode->NextNode = NULL;
      Tparent = CurNode->PrevNode;
   }

   /************************************************************/
   /* Section D  if CurNode is split root, create new root     */
   /************************************************************/

   /* at this point
       CurNode = The node that was just split
       TempNodeNo = The new node split off from CurNode */

   if(CurNode->NodeNo == HeadNode.StartNode ) 
   {
      TempNode = GetNodeMemory();
      if( !TempNode ) {
         xb_memory_error;
      }

      SaveNodeChain = NodeChain;
      NodeChain = NULL;
      SaveCurNode = CurNode;
      GetLastKey( CurNode->NodeNo, 0 );
      memcpy( KeyBuf, GetKeyData( CurNode->CurKeyNo,CurNode ),HeadNode.KeyLen );

      ReleaseNodeMemory( NodeChain );
      NodeChain = SaveNodeChain;
      CurNode = SaveCurNode;

      PutKeyData( 0, TempNode );
      PutLeftNodeNo( 0, TempNode, CurNode->NodeNo );
      PutLeftNodeNo( 1, TempNode, TempNodeNo );
      TempNode->NodeNo = HeadNode.TotalNodes++;
      TempNode->Leaf.NoOfKeysThisNode++;
      HeadNode.StartNode = TempNode->NodeNo;
      rc = PutLeafNode( TempNode->NodeNo, TempNode );
      if( rc ) return rc;
      rc = PutHeadNode( &HeadNode, indexfp, 1 );
      if( rc ) return rc;
      ReleaseNodeMemory( TempNode );
      return XB_NO_ERROR;
   }
   /**********************************/
   /* Section E  make room in parent */
   /**********************************/
   for( i = Tparent->Leaf.NoOfKeysThisNode; i > Tparent->CurKeyNo; i-- )
   {
      memcpy( KeyBuf, GetKeyData( i-1, Tparent ), HeadNode.KeyLen );
      PutKeyData( i, Tparent );
      PutLeftNodeNo( i+1, Tparent, GetLeftNodeNo( i, Tparent ));
   }

   /* put key in parent */

   SaveNodeChain = NodeChain;
   NodeChain = NULL;
   SaveCurNode = CurNode;
   GetLastKey( CurNode->NodeNo, 0 );

   memcpy( KeyBuf,GetKeyData( CurNode->CurKeyNo, CurNode ), HeadNode.KeyLen );

   ReleaseNodeMemory( NodeChain );
   NodeChain = SaveNodeChain;
   CurNode = SaveCurNode;

   PutKeyData( i, Tparent );
   PutLeftNodeNo( i+1, Tparent, TempNodeNo );
   Tparent->Leaf.NoOfKeysThisNode++;
   rc = PutLeafNode( Tparent->NodeNo, Tparent );
   if( rc ) return rc;
   rc = PutHeadNode( &HeadNode, indexfp, 1 );
   if( rc ) return rc;
 
   return XB_NO_ERROR;
}
/***********************************************************************/
//! Short description
/*!
  \param pos
  \param n
*/
xbShort xbNdx::RemoveKeyFromNode( xbShort pos, xbNdxNodeLink *n )
{
   xbShort i;

   /* check the node */
   if( !n )
     xb_error(XB_INVALID_NODELINK);

   if( pos < 0 || pos > HeadNode.KeysPerNode )
     xb_error(XB_INVALID_KEY);

   for( i = pos; i < n->Leaf.NoOfKeysThisNode-1; i++ )
   {
      memcpy( KeyBuf, GetKeyData( i+1, n), HeadNode.KeyLen );
   
      PutKeyData( i, n );
      PutDbfNo( i, n, GetDbfNo( i+1, n ));
      PutLeftNodeNo( i, n, GetLeftNodeNo( i+1, n ));
   }   
   PutLeftNodeNo( i, n, GetLeftNodeNo( i+1, n ));
   n->Leaf.NoOfKeysThisNode--;
   /* if last key was deleted, decrement CurKeyNo */
   if( n->CurKeyNo > n->Leaf.NoOfKeysThisNode )
      n->CurKeyNo--;
   return PutLeafNode( n->NodeNo, n );
}   
/***********************************************************************/
//! Short description
/*!
  \param n
*/
xbShort xbNdx::UpdateParentKey( xbNdxNodeLink * n )
{
/* this routine goes backwards thru the node chain looking for a parent
   node to update */

   xbNdxNodeLink * TempNode;
   
   if( !n )
     xb_error(XB_INVALID_NODELINK);

   if( !GetDbfNo( 0, n ))
      xb_error(XB_NOT_LEAFNODE);

   TempNode = n->PrevNode;
   while( TempNode )
   {
      if( TempNode->CurKeyNo < TempNode->Leaf.NoOfKeysThisNode )
      {
         memcpy(KeyBuf,GetKeyData(n->Leaf.NoOfKeysThisNode-1,n),HeadNode.KeyLen);
         PutKeyData( TempNode->CurKeyNo, TempNode );
         return PutLeafNode( TempNode->NodeNo, TempNode );
      }
      TempNode = TempNode->PrevNode;
   }
   return XB_NO_ERROR;
}
/***********************************************************************/
//! Short description
/*!
  \param n
*/
/* This routine queues up a list of nodes which have been emptied      */
void xbNdx::UpdateDeleteList( xbNdxNodeLink *n )
{
   n->NextNode = DeleteChain;
   DeleteChain = n;
}
/***********************************************************************/
//! Short description
/*!
*/
/* Delete nodes from the node list - for now we leave the empty nodes  */
/* dangling in the file. Eventually we will remove nodes from the file */

void xbNdx::ProcessDeleteList( void )
{
   if( DeleteChain )
   {
      ReleaseNodeMemory( DeleteChain );
      DeleteChain = NULL;
   }
}
/***********************************************************************/
//! Short description
/*!
*/
xbShort xbNdx::KeyWasChanged( void )
{
   CreateKey( 0, 0 );            /* use KeyBuf,  RecBuf    */
   CreateKey( 1, 1 );            /* use KeyBuf2, RecBuf2   */
   if( CompareKey( KeyBuf, KeyBuf2, HeadNode.KeyLen ) != 0 )
      return 1;
   else
      return 0;
}
/***********************************************************************/
//! Short description
/*!
  \param n
*/
xbNdxNodeLink * xbNdx::LeftSiblingHasSpace( xbNdxNodeLink * n )
{
   xbNdxNodeLink * TempNode;
   xbNdxNodeLink * SaveCurNode;

   /* returns a Nodelink to xbNdxNodeLink n's left sibling if it has space */

   /* if left most node in parent return NULL */
   if( n->PrevNode->CurKeyNo == 0 )  
      return NULL;

   SaveCurNode = CurNode;
   GetLeafNode( GetLeftNodeNo( n->PrevNode->CurKeyNo-1, n->PrevNode ), 2 ); 
   if( CurNode->Leaf.NoOfKeysThisNode < HeadNode.KeysPerNode )
   {
      TempNode = CurNode;  
      CurNode = SaveCurNode;
      TempNode->PrevNode = n->PrevNode;
      return TempNode;
   }
   else  /* node is already full */
   {
      ReleaseNodeMemory( CurNode );
      CurNode = SaveCurNode;
      return NULL;
   }
}
/***********************************************************************/
//! Short description
/*!
  \param n
*/
xbNdxNodeLink * xbNdx::RightSiblingHasSpace( xbNdxNodeLink * n )
{
 /* returns a Nodelink to xbNdxNodeLink n's right sibling if it has space */

   xbNdxNodeLink * TempNode;
   xbNdxNodeLink * SaveCurNode;

   /* if left most node in parent return NULL */
   if( n->PrevNode->CurKeyNo >= n->PrevNode->Leaf.NoOfKeysThisNode )  
      return NULL;

   SaveCurNode = CurNode;
   /* point curnode to right sib*/
   GetLeafNode( GetLeftNodeNo( n->PrevNode->CurKeyNo+1, n->PrevNode ), 2 ); 

   if( CurNode->Leaf.NoOfKeysThisNode < HeadNode.KeysPerNode )
   {
      TempNode = CurNode;  
      CurNode = SaveCurNode;
      TempNode->PrevNode = n->PrevNode;
      return TempNode;
   }
   else /* node is already full */
   {
      ReleaseNodeMemory( CurNode );
      CurNode = SaveCurNode;
      return NULL;
   }
}
/*************************************************************************/
//! Short description
/*!
  \param n
  \param Right
*/
xbShort xbNdx::MoveToRightNode( xbNdxNodeLink * n, xbNdxNodeLink * Right )
{
   xbShort j;
   xbNdxNodeLink * TempNode;
   xbNdxNodeLink * SaveCurNode;
   xbNdxNodeLink * SaveNodeChain;

   if( n->CurKeyNo == 0 )
   {
      j = 1;
      SaveNodeChain = NodeChain;
      SaveCurNode = CurNode;
      NodeChain = NULL;
      GetLastKey( n->NodeNo, 0 ); 
      memcpy( KeyBuf, GetKeyData( CurNode->CurKeyNo, CurNode),HeadNode.KeyLen);
      ReleaseNodeMemory( NodeChain );
      NodeChain = SaveNodeChain;
      CurNode = SaveCurNode;
   }
   else