' btxInsert   


'//
'//  Create a new LookupNode and link it to an already existing one.
'//
Function ctx_AddLookupNode_Internal( ByVal pBTX As BTX_TYPE Ptr, _
                                     ByVal CurrentLookupNode As INDEX_LOOKUP_NODE_TYPE Ptr, _
                                     ByVal CurrentLookupNodeNum As Long, _
                                     ByRef NewLookupNodeNum As Long _
                                      ) As Long

   Local NewLookupNode As INDEX_LOOKUP_NODE_TYPE
   
   ' We need to add another LookupNode
   If ctx_GetFreeNode_Internal( pBTX, NewLookupNodeNum ) Then GoTo ExitOut
   
   ' Link the previous node to this new node
   @CurrentLookupNode.NextNode = NewLookupNodeNum
   
   ' Save the current LookupNode to disk
   If ctx_PutNode_Internal( pBTX, CurrentLookupNodeNum, _
                            CurrentLookupNode ) Then GoTo ExitOut
   
   ' Save the new LookupNode to disk    
   If ctx_PutNode_Internal( pBTX, NewLookupNodeNum, _
                            VarPtr( NewLookupNode ) ) Then GoTo ExitOut

   Exit Function
   
ExitOut:
   Function = %ERR_FILEACCESS
    
End Function



'//
'//  Do a RegularNode node split and LookupNode split if necessary
'//
Function ctx_NodeSplit_Internal( ByVal pBTX As BTX_TYPE Ptr, _
                                 ByVal pTAG As INDEX_TAG_TYPE_MEMORY Ptr, _
                                 ByVal KeyAddress As Long, _
                                 ByVal KeyLength As Long, _
                                 ByVal RecNum As Long _
                                 ) As Long

   Local  pCurrentLookupNode   As INDEX_LOOKUP_NODE_TYPE Ptr
   Local  CurrentLookupNodeNum As Long
   Static TempNode             As INDEX_REGULAR_NODE_TYPE
   Static SplitNode            As INDEX_REGULAR_NODE_TYPE
   Local  SplitNodeNum         As Long
   Local  LookupNodePos_Split  As Long
   Local  LookupKeyToMove      As String
   Local  LookupNodeNumToMove  As Long
   Local  InsertAddress        As Long
   Local  NextLookupNode       As Long
   Local  LastLookupKey        As String
   Local  LastLookupNodeNum    As Long
   Local  x                    As Long
   Local  nFound               As Long
   
   ' We will now take the current RegularNode and split it into two
   ' parts. Half of the the node will stay in the current RegularNode
   ' while the second half will be copied to new SplitNode.
   
   ' Determine the current LookupNodePos. This LookupKey may be
   ' updated if the first key was affected. The first key from
   ' the new SplitNode is inserted immediately following the
   ' current LookupNodePos.
   For x = 1 To %INDEX_MAX_LOOKUP_KEYS
      If @pTAG.LookupNode.Node(x) = @pTAG.RegularNodeNum Then
         @pTAG.LookupNodePos = x
         Exit For
      End If
   Next                      

   ' The SplitNode is a new node so we need to get a position in the
   ' index to put it. Get a node number from the Free list or add it
   ' to the end of the file.   
   If ctx_GetFreeNode_Internal( pBTX, SplitNodeNum ) Then GoTo ExitOut

   ' Copy the second half of the node to the SplitNode variable.
   MemCopyD VarPtr(@pTAG.RegularNode.Buffer) + ( @pTAG.@pTagDisk.HalfNode * (KeyLength + 4)), _
            VarPtr(SplitNode.Buffer), _                   
            @pTAG.@pTagDisk.HalfNode * (KeyLength + 4)                                   
               

   ' Link the two nodes together
   If @pTAG.RegularNode.NextNode = 0 Then
       ' Scenario #1: RegularNode.NextNode did not exist prior to split
       '
       '     LEFTNODE 
       '   (RegularNode)      
       '
       '     LEFTNODE      <-->     RIGHTNODE
       '   (RegularNode)          (NewSplitNode)
       @pTAG.RegularNode.NextNode = SplitNodeNum
       SplitNode.NextNode         = 0
       SplitNode.PrevNode         = @pTAG.RegularNodeNum
    
   Else
       ' If the original Left node was already pointing to a Right node then we
       ' need to update that node to point back to the new right node. This is because the
       ' new node is inserted between the original two nodes.
      
       ' Scenario #2: RegularNode.NextNode existed prior to split
       '
       '     LEFTNODE       <-->     RIGHTNODE
       '   (RegularNode)          (RegularNode.NextNode)
       '
       '     LEFTNODE       <-->   NEWRIGHTNODE     <-->      RIGHTNODE
       '   (RegularNode)          (NewSplitNode)         (RegularNode.NextNode)
       '       (1)                     (2)                       (3)

       ' Get the RegularNode.NextNode and link it back to the NewSplitNode
       If ctx_GetNode_Internal( pBTX, @pTAG.RegularNode.NextNode, _
                                VarPtr( TempNode ) ) Then GoTo ExitOut

       ' Link the nodes... (2) to (3)
       TempNode.PrevNode  = SplitNodeNum
       SplitNode.NextNode = @pTAG.RegularNode.NextNode

       ' Write it back to disk
       If ctx_PutNode_Internal( pBTX, @pTAG.RegularNode.NextNode, _
                                VarPtr(TempNode) ) Then GoTo ExitOut
       
       ' Link the current RegularNode to the NewSplitNode (1) to (2)
       @pTAG.RegularNode.NextNode = SplitNodeNum
       SplitNode.PrevNode         = @pTAG.RegularNodeNum

   End If
       
   ' Adjust the keycount in each node
   @pTAG.RegularNode.NumKeys  = @pTAG.@pTagDisk.HalfNode
   SplitNode.NumKeys          = @pTAG.@pTagDisk.HalfNode
   
   ' Determine in which node the new key will fall into 
   If @pTAG.RegularNodePos > @pTAG.@pTagDisk.HalfNode Then
      ' Right node: SplitNode
      InsertAddress = VarPtr(SplitNode.Buffer)
      Incr SplitNode.NumKeys
      @pTAG.RegularNodePos = @pTAG.RegularNodePos - @pTAG.@pTagDisk.HalfNode 
   Else
      ' Left node: @pTAG.RegularNode
      InsertAddress = VarPtr(@pTAG.RegularNode.Buffer)
      Incr @pTAG.RegularNode.NumKeys
   End If   
      
   ' Insert the Key string
   MemInsert InsertAddress, _
              Len(@pTAG.RegularNode.Buffer), _
              (@pTAG.RegularNodePos-1) * ( KeyLength + 4 ), _
              KeyAddress, _
              KeyLength + 4   ' 4 is to allow space for the record number
   
   ' Insert the record number
   MemCopyD VarPtr(RecNum), _
            InsertAddress + ( (@pTAG.RegularNodePos-1) * ( KeyLength + 4 ) ) + KeyLength, _
            4
      
   ' Write the RegularNode back to disk
   If ctx_PutNode_Internal( pBTX, @pTAG.RegularNodeNum, _
                            VarPtr( @pTAG.RegularNode ) ) Then GoTo ExitOut
                            
   ' Write the new split node to disk
   If ctx_PutNode_Internal( pBTX, SplitNodeNum, _
                            VarPtr(SplitNode) ) Then GoTo ExitOut
                    
                    
  
   ' We will definately have to insert the first key in the SplitNode to
   ' the LookupNode linked list. We'll also have to insert the first key
   ' of the RegularNode if the first key in that node was affected. The
   ' LookupNode currently loaded is for the RegularNode.
   If ( InsertAddress = VarPtr(@pTAG.RegularNode.Buffer) ) And _
      ( @pTAG.RegularNodePos = 1 ) Then
      
      MemCopyD KeyAddress, _
               VarPtr(@pTAG.LookupNode.Key(@pTAG.LookupNodePos)), _
               Min( 4, KeyLength )
      @pTAG.LookupNode.Node(@pTAG.LookupNodePos) = @pTAG.RegularNodeNum
      If ctx_PutNode_Internal( pBTX, @pTAG.LookupNodeNum, _
                               VarPtr( @pTAG.LookupNode ) ) Then GoTo ExitOut
   End If                                                     
   

   
   ' Now, try to insert the new LookupNode key/node for the new SplitNode
   ' into the linked list of LookupNodes. The position will be one greater
   ' than the current position because the split should be immediately to
   ' the right of the current node.
   pCurrentLookupNode   = VarPtr( @pTAG.LookupNode )
   CurrentLookupNodeNum = @pTAG.LookupNodeNum
   LookupNodePos_Split  = @pTAG.LookupNodePos + 1  
   LookupKeyToMove      = Peek$( VarPtr(SplitNode.Buffer), Min(4, KeyLength) )
   LookupNodeNumToMove  = SplitNodeNum
   nFound               = %FALSE

   
   ' Test to see if the split is spawning two LookupNodes
   If LookupNodePos_Split > %INDEX_MAX_LOOKUP_KEYS Then
      LookupNodePos_Split = 1
      
      ' Load the next LookupNode
      NextLookupNode = @pTAG.LookupNode.NextNode
      
      If NextLookupNode = 0 Then
         ' Add a new LookupNode. This automatically links the current
         ' LookupNode to it (i.e. @pTAG.LookupNode.NextNode is set).
         If ctx_AddLookupNode_Internal( pBTX, pCurrentLookupNode, _
                                        CurrentLookupNodeNum, _
                                        @pTAG.LookupNodeNum ) Then GoTo ExitOut
         
      Else
         
         @pTAG.LookupNodeNum = NextLookupNode
         
      End If                
            
      If ctx_GetNode_Internal( pBTX, @pTAG.LookupNodeNum, _
                               VarPtr( @pTAG.LookupNode ) ) Then GoTo ExitOut
      
      pCurrentLookupNode   = VarPtr( @pTAG.LookupNode )
      CurrentLookupNodeNum = @pTAG.LookupNodeNum
   End If
      
      
   Do 
      
      LastLookupKey     = @pCurrentLookupNode.Key(%INDEX_MAX_LOOKUP_KEYS) 
      LastLookupNodeNum = @pCurrentLookupNode.Node(%INDEX_MAX_LOOKUP_KEYS)

      ' Can we fit the key into the current LookupNode? 
      If @pTAG.LookupNode.Node(%INDEX_MAX_LOOKUP_KEYS) = 0 Then
         nFound = %TRUE
      End If

      ' Make room in the LookupNode 
      For x = %INDEX_MAX_LOOKUP_KEYS To LookupNodePos_Split + 1 Step -1
          @pCurrentLookupNode.Key(x)  = @pCurrentLookupNode.Key(x-1)
          @pCurrentLookupNode.Node(x) = @pCurrentLookupNode.Node(x-1)
      Next
      @pCurrentLookupNode.Key(LookupNodePos_Split)  = LookupKeyToMove     
      @pCurrentLookupNode.Node(LookupNodePos_Split) = LookupNodeNumToMove

      If ctx_PutNode_Internal( pBTX, CurrentLookupNodeNum, _
                               pCurrentLookupNode ) Then GoTo ExitOut
                               
      If nFound = %TRUE Then Exit Do                          
      
      LookupNodePos_Split = 1
      LookupKeyToMove     = LastLookupKey     
      LookupNodeNumToMove = LastLookupNodeNum 
      
      NextLookupNode = @pCurrentLookupNode.NextNode
      
      If NextLookupNode = 0 Then
         ' Add a new LookupNode. This automatically links the current
         ' LookupNode to it (i.e. @pTAG.LookupNode.NextNode is set).
         If ctx_AddLookupNode_Internal( pBTX, pCurrentLookupNode, _
                                        CurrentLookupNodeNum, _
                                        @pTAG.LookupNodeNum ) Then GoTo ExitOut
         
      Else
         
         @pTAG.LookupNodeNum = NextLookupNode
         
      End If                
            
      If ctx_GetNode_Internal( pBTX, @pTAG.LookupNodeNum, _
                               VarPtr( @pTAG.LookupNode ) ) Then GoTo ExitOut
                               
      pCurrentLookupNode   = VarPtr( @pTAG.LookupNode )
      CurrentLookupNodeNum = @pTAG.LookupNodeNum
   
   Loop
      
      
   Exit Function
   
ExitOut:
   Function = %ERR_FILEACCESS
    
End Function



'//
'//  Insert a key into a Tag/Index.
'//
Function ctx_InsertKey_Internal( ByVal xdb As CHEETAH4_TYPE Ptr ) As Long
   
   Local pBTX            As BTX_TYPE Ptr
   Local pTagDisk        As INDEX_TAG_TYPE_DISK Ptr
   Local pTAG            As INDEX_TAG_TYPE_MEMORY Ptr
   Local KeyAddress      As Long
   Local KeyLength       As Long
   Local RecNum          As Long 
   Local nFound          As Long 
   Local sTempKey        As String
   
   ' Do some tests to ensure that the parameters were correctly
   ' filled in when the call was made.
   If (@xdb.nData = 0)      Or (@xdb.nLen = 0)     Or _
      (@xdb.nData4byte = 0) Or (@xdb.reserved = 0) Then
      @xdb.errcode = %ERR_DATA: GoTo ExitOut
   End If
   
   KeyAddress = @xdb.nData
   KeyLength  = @xdb.nLen
   RecNum     = @xdb.nData4byte

   ' The Tag disk structure (from the index header) is in the reserved element
   pTAG = @xdb.reserved
   
   ' Get the associated index... 
   pBTX = @pTAG.pBTX

   ' If the incoming Key is not the correct size then we must create a
   ' buffer to put it in, otherwise, the insertion routines will not
   ' create a full, blank, space in which the new key will be inserted
   ' in the node (e.g. an incoming key of length 5 would not cover the entire
   ' space needed for a defined key length of 7 resulting in possibly
   ' two garbage characters appearing after the newly inserted key).
   If KeyLength <> @pTAG.@pTagDisk.KeySize Then
      sTempKey = Space$( @pTAG.@pTagDisk.KeySize )
      LSet sTempKey = Peek$( KeyAddress, KeyLength )
      KeyAddress = StrPtr( sTempKey )
      KeyLength  = @pTAG.@pTagDisk.KeySize
   End If       
   
   If @pTAG.@pTagDisk.UpperCase Then 
      Poke$ KeyAddress, UCase$(Peek$(KeyAddress, KeyLength))
   End If

   
   ' Position the node to where the key should be inserted
   nFound = ctx_SeekEngine_Internal( xdb, pBTX, pTAG, _
                                     KeyAddress, KeyLength, _
                                     RecNum, %XDB_SEEK_INSERT )

   
   ' If no RegularNode exists then we need to get a free node
   ' to put it in (from the Free list or end of the index itself)
   If @pTAG.RegularNodeNum = 0 Then
      @xdb.errcode = ctx_GetFreeNode_Internal( pBTX, @pTAG.RegularNodeNum )
      If @xdb.errcode Then GoTo ExitOut
      Type Set @pTAG.RegularNode = ""
   End If
                                          
   ' If the insert position was not found then insert at the end of the node.
   If nFound = %FALSE Then
      @pTAG.RegularNodePos = @pTAG.RegularNode.NumKeys + 1
   End If
         
   
   ' The key will now be inserted, but we need to determine if the key will
   ' cause a node split. The node split function is fully self-contained and
   ' will handle the adding of the current key/recnum as well as updating
   ' the RegularNode and LookupNodes. It will also write any affected nodes
   ' to disk.
   If @pTAG.RegularNode.NumKeys + 1 > @pTAG.@pTagDisk.MaxKeys Then
      @xdb.errcode = ctx_NodeSplit_Internal( pBTX, pTAG, KeyAddress, KeyLength, RecNum )
      If @xdb.errcode Then GoTo ExitOut
      Exit Function
   End If      
             
             
   
   '// JUST A NORMAL INSERT INTO THE NODE... //
   Incr @pTAG.RegularNode.NumKeys

   ' Insert the Key string
   MemInsert VarPtr(@pTAG.RegularNode.Buffer), _
              Len(@pTAG.RegularNode.Buffer), _
              (@pTAG.RegularNodePos-1) * ( KeyLength + 4 ), _
              KeyAddress, _
              KeyLength + 4   ' 4 is to allow space for the record number
   
   ' Insert the record number
   MemCopyD VarPtr(RecNum), _
            VarPtr(@pTAG.RegularNode.Buffer) + ( (@pTAG.RegularNodePos-1) * ( KeyLength + 4 ) ) + KeyLength, _
            4
   
      
   ' Write the RegularNode back to disk
   @xdb.errcode = ctx_PutNode_Internal( pBTX, _
                                        @pTAG.RegularNodeNum, _
                                        VarPtr( @pTAG.RegularNode ) )
   If @xdb.errcode Then GoTo ExitOut
   
   
   ' If the key was added in the first position of the node then we
   ' need to update the key that is reflected in the LookupNode.
   If @pTAG.RegularNodePos = 1 Then

      MemCopyD KeyAddress, _
               VarPtr(@pTAG.LookupNode.Key(@pTAG.LookupNodePos)), _
               Min( 4, KeyLength )
      @pTAG.LookupNode.Node(@pTAG.LookupNodePos) = @pTAG.RegularNodeNum

      ' Write the LookupNode back to disk because it was updated
      @xdb.errcode = ctx_PutNode_Internal( pBTX, _
                                           @pTAG.LookupNodeNum, _
                                           VarPtr( @pTAG.LookupNode ) )
      If @xdb.errcode Then GoTo ExitOut
   End If
   
   
ExitOut:
   Function = @xdb.errcode 
    
End Function




'//
'//  Generate the key that needs to be added to the index TAG.
'//
Function ctx_GenerateIndexKey_Internal( ByVal pDBF As DBF_TYPE Ptr, _
                                        ByVal pTAG As INDEX_TAG_TYPE_MEMORY Ptr, _
                                        ByVal UseOriginalBuffer As Long _
                                        ) As String
                                        
   Local sIndexKey As String
   Local nFieldNum As Long             
   Local nOffset   As Long
   Local x         As Long
   
   Local pRecordBuffer As Dword
   
   If UseOriginalBuffer Then
      pRecordBuffer = @pDBF.pRecordBuffer_Original
   Else
      pRecordBuffer = @pDBF.pRecordBuffer
   End If
   
   ' Create the string that will hold the entire key. We do this
   ' rather than using concatenation because it is much faster.
   sIndexKey = String$( @pTAG.@pTagDisk.KeySize, 0 )
 
   
   For x = 1 To %INDEX_MAX_TAG_FIELDS
    
      nFieldNum = @pTAG.@pTagDisk.Fields(x) - 1   ' b/c fields are zero based
      
      If nFieldNum >= 0 Then
         
         Select Case Long Asc( @pDBF.@pFields[nFieldNum].FieldType )
      
            Case 67, 68, 78, 70, 76  ' "C", "D", "N", "F", "L"
               MemCopyD pRecordBuffer + @pDBF.@pFields[nFieldNum].FDA, _
                        StrPtr(sIndexKey) + nOffset, _
                        @pDBF.@pFields[nFieldNum].FieldLength
               nOffset = nOffset + @pDBF.@pFields[nFieldNum].FieldLength
             
            Case 89, 84, 66  'Y, T, B
               '@xdb.nData8byte = Peek(Double, @xdb.nData)
             
            Case 73  ' I
               '@xdb.nData4byte = Peek(Long, @xdb.nData)
         End Select
         
      End If
    
   Next
   
   If @pTAG.@pTagDisk.UpperCase Then sIndexKey = UCase$(sIndexKey)
   
   Function = sIndexKey 
   
End Function


