' btxSeek


Function ctx_Seek_Internal( ByVal xdb As CHEETAH4_TYPE Ptr ) As Long
   
   Local pBTX            As BTX_TYPE Ptr
   Local pTAG            As INDEX_TAG_TYPE_MEMORY Ptr
   Local KeyAddress      As Long
   Local KeyLength       As Long
   Local nResult         As Long
   
   ' Do some tests to ensure that the parameters were correctly
   ' filled in when the call was made.
   If @xdb.reserved = 0 Then
      @xdb.errcode = %ERR_DATA: GoTo ExitOut
   End If
   
   pTAG = @xdb.reserved
   pBTX = @pTAG.pBTX      ' get the associated index for this TAG

   KeyAddress = @xdb.nData
   KeyLength  = @xdb.nLen  
   
   nResult = ctx_SeekEngine_Internal( xdb, pBTX, pTAG, _
                                      KeyAddress, KeyLength, _
                                      0, %XDB_SEEK_KEYONLY )
   
   ' Determine what type of "error code" to return to the 
   ' calling function. The nResult variable holds the type
   ' of result that the search yielded. It is possible, however, 
   ' that an Error occurred during the search. That error code
   ' must override the search result.
   If @xdb.errcode Then
      Function = @xdb.errcode: Exit Function
   End If
   
   
   ' Return to the user the status of the seek.   
   Select Case nResult        
   
      Case %FALSE   ' no match was found
         Function = %ERR_SEEKNOMATCH
   
      Case %TRUE
         ' A match was found but if the keylength being searched for
         ' was not the exact size then we only have a partial match.
         If @pTAG.@pTagDisk.KeySize <> KeyLength Then
            Function = %ERR_SEEKPARTIALMATCH 
         Else
            Function = %ERR_SEEKEXACTMATCH   
         End If
      
   End Select   

Exit Function
       
ExitOut:
   Function= @xdb.errcode  

End Function



'//
'//  The SeekEngine function handles all of the Cheetah seeks of the
'//  Tag file (i.e. for both Insertions and regular Seek lookups)
'//
Function ctx_SeekEngine_Internal( ByVal xdb As CHEETAH4_TYPE Ptr, _
                                  ByVal pBTX As BTX_TYPE Ptr, _
                                  ByVal pTAG As INDEX_TAG_TYPE_MEMORY Ptr, _
                                  ByVal KeyAddress As Long, _
                                  ByVal KeyLength As Long, _
                                  ByVal nRecNum As Long, _
                                  ByVal SeekTypeFlag As Long _
                                  ) As Long
                                  
   Local RecNum          As Long 
   Local x               As Long
   Local NextRegularNode As Long
   Local NextLookupNode  As Long
   Local nResult         As Long
   Local nFound          As Long  
   Local KeyRecNum       As Long
   Local PrevLookupNode  As Long

   '// SEARCH THE LOOKUPNODE ARRAY OF KEYS 
   
   ' Determine where to put the new key. Search the LookupNode to find
   ' the correct node to put the new key in. First, load the LookupNode
   ' if it is not already loaded.          
   NextLookupNode      = @pTAG.@pTagDisk.FirstLookupNode
   @pTAG.LookupNodePos = 1
   
   PrevLookupNode = 0
   nFound = %FALSE
   
   Do Until NextLookupNode = 0                  
      
      If (@pTAG.LookupNodeNum <> NextLookupNode) Or _
         (@pBTX.MultiUser = %TRUE) Then
      
         @xdb.errcode = ctx_GetNode_Internal( pBTX, _
                                              NextLookupNode, _
                                              VarPtr( @pTAG.LookupNode ) )
         If @xdb.errcode Then GoTo ExitOut    
         @pTAG.LookupNodeNum = NextLookupNode 
      
      End If
      
          
      ' Search for the LookupNode position that holds the RegularNode where
      ' the incoming key being searched for should fall. Sequential scan.
      For x = 1 To %INDEX_MAX_LOOKUP_KEYS

         ' If the pointer to the RegularNode is zero then we can use this
         ' position rather than continue to keep looking.
         If @pTAG.LookupNode.Node(x) = 0 Then Exit For
            
         ' If the key being added is less than or equal to the LookupNode
         ' key value then we add the key at this LookUpNode position.
         If StrCmp3( KeyAddress, _
                     VarPtr( @pTAG.LookupNode.Key(x) ), _
                     Min( KeyLength, 4 ) ) <= 0 Then
            nFound = %TRUE                          
            Exit For
         End If

         @pTAG.LookupNodePos = x

      Next
      
      ' SPECIAL SITUATION WHERE THE KEY MAY FALL BETWEEN TWO LOOKUP NODES
      ' If the match was found at the first RegularNodePos then we need
      ' to start looking for an insertion point in the node immediately
      ' before the node referenced by the LookupNode. This satisfies the 
      ' condition where the key being searched for is greater than the
      ' key held in the LookupNode.Key(%INDEX_MAX_LOOKUP_KEYS) but is
      ' less than the LookupNode.Key(1) key of the next LookupNode that
      ' will get loaded. We also need to reload the previous LookupNode
      ' and reposition to the %INDEX_MAX_LOOKUP_KEYS position to ensure
      ' that the internal buffer is correct.
      If (nFound = %TRUE) And (@pTAG.LookupNodePos = 1) And _
         (PrevLookupNode <> 0 ) Then
      
         @xdb.errcode = ctx_GetNode_Internal( pBTX, _
                                              PrevLookupNode, _
                                              VarPtr( @pTAG.LookupNode ) )
         If @xdb.errcode Then GoTo ExitOut    

         @pTAG.LookupNodeNum = PrevLookupNode
         @pTAG.LookupNodePos = %INDEX_MAX_LOOKUP_KEYS
         Exit Do
      End If
      
      
      ' If we have found a valid LookupNode position then exit
      ' our search, otherwise continue to look at the next 
      ' LookupNode in the linked list.
      If nFound = %TRUE Then Exit Do
      
      PrevLookupNode = NextLookupNode
      
      NextLookupNode = @pTAG.LookupNode.NextNode
      @pTAG.LookupNodePos = 1
      
   Loop
                                                        

   
   '// SEARCH THE REGULARNODE TO DETERMINE INSERTION/MATCH POINT
   
   NextRegularNode      = @pTAG.LookupNode.Node(@pTAG.LookupNodePos)
   @pTAG.RegularNodePos = 1
   
   Do Until NextRegularNode = 0                  
   
      If (@pTAG.RegularNodeNum <> NextRegularNode) Or _
         (@pBTX.MultiUser = %TRUE) Then

         @xdb.errcode = ctx_GetNode_Internal( pBTX, _
                                              NextRegularNode, _
                                              VarPtr( @pTAG.RegularNode ) )
         If @xdb.errcode Then GoTo ExitOut
         @pTAG.RegularNodeNum = NextRegularNode
      End If

      nFound = %FALSE

      ' Perform a binary search on the node to find the starting point for
      ' the sequential scan. We continue looking until searched key is less
      ' than the key on the node. Doing this rather than immediately starting
      ' at the beginning of the node allows us to speed up the seek by 10% to 15%.
      Local minimum As Long
      Local maximum As Long
      Local nStartPos As Long
      
      nStartPos = 1
      minimum   = 1
      maximum   = @pTAG.RegularNode.NumKeys 

      Do While minimum <= maximum
         
         x = (maximum + minimum) / 2
         
         If StrCmp3( ByVal VarPtr( @pTAG.RegularNode.Buffer ) + ( (x-1) * (@pTAG.@pTagDisk.KeySize+4)), _ 
                     ByVal KeyAddress, _
                     ByVal KeyLength ) = -1 Then
            nStartPos = x         
            Exit Do
         Else            
            ' Greater or Equal Than (the key in the node is bigger than the incoming key)
            maximum = x - 1   ' keep searching
         End If

      Loop                     
      
             
      For x = nStartPos To @pTAG.RegularNode.NumKeys

         ' Search until the Key is greater than the key in the node. If the
         ' keys are equal then continue searching until the incoming record 
         ' number is greater than the record number on the node. That is, 
         ' duplicate Keys will be stored with record numbers in descending
         ' sequence.
         
         ' If the key being added is less than or equal to the 
         ' key value then we add the key at this position.
         nResult = StrCmp3( ByVal KeyAddress, _
                            ByVal VarPtr( @pTAG.RegularNode.Buffer ) + ( (x-1) * (@pTAG.@pTagDisk.KeySize+4)), _ 
                            ByVal KeyLength ) 
         
         'nResult = CompareString( ByVal %LOCALE_SYSTEM_DEFAULT, _ 
         '                         ByVal 0, _ 
         '                         ByVal VarPtr( @pTAG.RegularNode.Buffer ) + ( (x-1) * (@pTAG.@pTagDisk.KeySize+4)), _ 
         '                         ByVal KeyLength, _
         '                         ByVal KeyAddress, _
         '                         ByVal KeyLength ) - 2

         @pTAG.RegularNodePos = x 

         KeyRecNum = Peek( Long, VarPtr(@pTAG.RegularNode.Buffer) + _
                           ( (x-1) * ( @pTAG.@pTagDisk.KeySize + 4 ) ) + @pTAG.@pTagDisk.KeySize ) 
         
         Select Case As Long nResult
            Case  0    ' Equal 
               ' If the keys are equal then we further sort based on record number if
               ' we are performing an insert operation, otherwise simply exit.
               
               Select Case SeekTypeFlag
                  
                  Case %XDB_SEEK_INSERT         
                     If nRecNum > KeyRecNum Then
                        RecNum = KeyRecNum                  
                        nFound = %TRUE
                        Exit For
                     End If               
               
                  Case %XDB_SEEK_KEYONLY       
                     ' We are performing a simple Seek operation. Return the RecNum
                     ' associated with this Key.
                     RecNum = KeyRecNum                  
                     nFound = %TRUE
                     Exit For
                  
                  Case %XDB_SEEK_KEY_AND_RECNUM 
                     If nRecNum = KeyRecNum Then
                        nFound = %TRUE
                        Exit For
                     End If               
               
               End Select
               
            Case -1    ' Less Than or partial match
               If SeekTypeFlag = %XDB_SEEK_INSERT Then
                  RecNum = KeyRecNum                  
                  nFound = %TRUE
                  Exit For
               End If
               
            Case +1    ' Greater Than (the key in the node is bigger than the incoming key)
               ' Continue searching.... 
         End Select
            
      Next
      

      ' If we have found a valid LookupNode position then exit
      ' our search, otherwise continue to look at the next 
      ' LookupNode in the linked list.
      If nFound = %TRUE Then Exit Do
      
         
      NextRegularNode = @pTAG.RegularNode.NextNode   
      NextLookupNode  = @pTAG.LookupNode.NextNode
      
      Incr @pTAG.LookupNodePos
      

      ' If an insertion/match position has still not been found then we
      ' need to move to the next node in the linked list of RegularNodes.
      If ( @pTAG.LookupNodePos > %INDEX_MAX_LOOKUP_KEYS ) Then 
         If NextLookupNode = 0 Then
            @pTAG.LookupNodePos = %INDEX_MAX_LOOKUP_KEYS
            Exit Do
         End If

         ' Another LookupNode exists so start looking at it
         @xdb.errcode = ctx_GetNode_Internal( pBTX, _
                                              NextLookupNode, _
                                              VarPtr( @pTAG.LookupNode ) )
         If @xdb.errcode Then GoTo ExitOut                     
         @pTAG.LookupNodeNum = NextLookupNode
         @pTAG.LookupNodePos = 1
      End If
      
   Loop
   
   
   ' Return the record number in the nData4byte element
   @xdb.nData4byte = RecNum 

   ' Save the last used data in case a MoveNext, etc occurs.
   MemString @pTAG.zLastMoveKey, Peek$(VarPtr(@pTAG.RegularNode.Buffer) + ((@pTAG.RegularNodePos-1) * (@pTAG.@pTagDisk.KeySize+4)), @pTAG.@pTagDisk.KeySize)
   @pTAG.nLastMoveRecNum = RecNum

ExitOut:
   Function = nFound
   
End Function

                          
'//
'//  Retrieve the current index TAG Key/Recnum 
'//                          
Function ctx_GetKey_Internal( ByVal xdb As CHEETAH4_TYPE Ptr ) As Long
   
   Local pTAG    As INDEX_TAG_TYPE_MEMORY Ptr
   Local nOffset As Long
   
   ' Do some tests to ensure that the parameters were correctly
   ' filled in when the call was made.
   If @xdb.reserved = 0 Then
      @xdb.errcode = %ERR_DATA: GoTo ExitOut
   End If
   
   pTAG = @xdb.reserved

   nOffset    =  (@pTAG.RegularNodePos-1) * (@pTAG.@pTagDisk.KeySize+4) 
   @xdb.nData = VarPtr(@pTAG.RegularNode.Buffer) + nOffset 
   @xdb.nLen  = @pTAG.@pTagDisk.KeySize
   
   ' Return the record number in the nData4byte element
   @xdb.nData4byte = Peek( Long, VarPtr(@pTAG.RegularNode.Buffer) + nOffset + @pTAG.@pTagDisk.KeySize)

ExitOut:
   Function = @xdb.errcode

End Function
