   Dim Version$/"Key File Validation Program V1.0",...
&               " (C) 1985 Software Dynamics, Inc."/
   ! This program validates files produced by KEY.BAS
   ! Errors are reported if found, or a clean bill of health given.
   ! Files which have reported errors should not ever be used.
   ! Files which have a clean bill of health are perfectly safe to use.
   ! This program should be run once a week on large databases,
   ! but is NOT a substitute for appropriate backup procedures.
   !
   ! Conventions used in this program are those of the Key file package.

   ! ALL VARIABLES/ROUTINES USED BY THIS PACKAGE ARE NAMED "KEYxxxxx"

   DIM KEYROOTSIZE/24/,KEYSIZE,KEYMAXKEYCOUNT,KEYROOT,KEYFREE
   DIM KEYCHANNEL/1/,KEYNUMBER

   DIM KEY$[64],KEYTEMP$[64]
   Dim KeyPrevious$[64],KeyMinKey$[64],KeyMaxKey$[64]

   ! Error code which signifies that KeyNumber selects malformed Key structure
   Dim BadKeyFile/1077/
   DIM SCgetfilesize$/:F,14,0,:3/

   Dim KeyNodeStackAddress(20),KeyNodeStackKeyCount(20)
   Dim KeyNodeStackNextKey(20),KeyNodeStackMaxKey$(20)[64]

   Dim Temp$(50)

DEF KEYPOINTERPAIR(KEYPOINTERPAIRNODE,KEYPOINTERPAIRSELECTOR)
    REM RETURN POINTER TO PAIRSELECTORth KEYPOINTERPAIR
    REM ASSERT: 0<=PAIRSELECTOR<=KEYCOUNT
    RETURN KEYPOINTERPAIRNODE+6+KEYPOINTERPAIRSELECTOR*(6+KEYSIZE)
END

Def ReportAndQuery(ReportMessage$)
   ! Function to display message and ask User a Yes/No question.
   ! A <CR> is a default YES response
   ! Returns TRUE if YES, FALSE if NO.
   Print ReportMessage$;
   Repeat
      Input '' Temp$
      Let Temp$=UpperCase$(Temp$)
      If Temp$="" or Find(Temp$,"Y")=1 Then Return True
      If Find(Temp$,"N")=1 Then Return False
      Print "YES or NO only, please: "
   End
End

Def ChunkConflict(ChunkBase,ChunkLength)
   ! This function records the fact that the part of the file starting
   ! at ChunkBase is busy for ChunkLength bytes.
   ! It validates Chunkbase to make sure it points INTO the file,
   ! and that ChunkBase+ChunkLength is less or equal to file size.
   ! Returns TRUE if a problem exists.
   ! We assert that ChunkLength is a reasonable positive integer.
   If ChunkBase<0 or ChunkBase<>int(ChunkBase) ...
&  or ChunkBase+ChunkLength>FileSize
   Then
       Print "Bad Pointer"
       Return True
   Fi
   ! HERE WE SHOULD LOOK CHUNK UP IN LIST OF RECORDED CHUNKS.
   ! IF A CONFLICT OCCURS, WE SHOULD COMPLAIN.
   ! IF NO CONFLICT OCCURS, WE SHOULD RECORD THE CHUNK
   ! (COALESCING CHUNKS AS NEEDED TO KEEP SEARCH TIMES DOWN)
   Return False \ ! No chunk conflict found.
End

! **** MAIN PROGRAM BEGINS HERE ****
   If Col(0)>0
   Then
       ! User supplied name of file on command line
       Input "" Key$
       Print Version$
   Else
       ! User invoked program but did not give file name
       Print Version$
       Input "Name of key file to validate: " Key$
   Fi
   KeyChannel=1 \ ! Which channel to perform Keyed File I/O upon.
   Open #KeyChannel,Key$ \ ! Open the file
   Print "Key file must not be in use while this program is running."
   ! ASSERT: CONTENTS OF FILE DOES NOT CHANGE WHILE THIS PROGRAM RUNS.
   ! WE ALSO ASSUME CORRECT OPERATION OF PROGRAM, SDOS, COMPUTER AND DISK.
   ! Determine size of file in bytes.
   Syscall #KeyChannel,SCgetfilesize$,"",Key$
   FileSize=Key$[1]*256^3+Key$[2]*256^2+Key$[3]*256+Key$[4]
! *** Rather than having negative pointers in tree, we could keep
! *** tree depth in tree node head.  Then files with 2^32 bytes would
! *** really be possible!!!!! Fix this in next key file package.
!^L
   Input "Key Number to validate: " KeyNumber
   ! Read Head of B-tree from file.
   Read #KeyChannel@KeyRootSize*(KeyNumber-1),...
&           KeySize,KeyMaxKeyCount,KeyRoot,KeyFree
   Print "Key Size = ";KeySize
   Print "Maximum keys per node: ";KeyMaxKeyCount
   ! RESET LIST OF BUSY CHUNKS HERE
   ! All places at or below Key Tree Root are busy.
   If ChunkConflict(0,KeyRootSize*KeyNumber)
   Then Print "Program Bug!"\Error 101
   ! Validate Head of B-tree
   If KeySize<=0 or KeySize<>int(KeySize) or KeySize>63
   Then
       Print "KeySize is damaged. Validation terminated."
       Error BadKeyFile
   Fi
   If KeyMaxKeyCount<4 or KeyMaxKeyCount<>int(KeyMaxKeyCount) ...
&  Or KeyMaxKeyCount>127
   Then
       Print "MaxKeyCount per node is damaged. Validation terminated."
       Error BadKeyFile
   Fi
   ! Compute size of node in B-Tree
   !   ...requires room for KeyMaxKeyCount (Key,Ptr) pairs
   !   ...plus room for a KeyCount and a Rightmost son pointer
   KeyNodeSize=12+KeyMaxKeyCount*(KeySize+6)
   If KeyRoot<0 or KeyRoot<>int(KeyRoot) or ...
&     KeyRoot>FileSize-KeyNodeSize and KeyRoot<>0
   Then
       Print "Pointer (";KeyRoot;") to B-tree root node is ruined. Validation terminated."
       Error BadKeyFile
   Fi

   If KeyFree<>0
   Then
       Print "Validating list of free B-tree nodes."
       ! A pointer to a list of free B-tree nodes is present.
       ! Follow links and verify that they are all valid.
       KeyNodePointer=KeyFree \ ! 1st block address
       Repeat
           If ChunkConflict(KeyNodePointer,KeyNodeSize)
           Then
               If ReportAndQuery(...
&                     "Free Node Chain garbled. Reset (Default=Y)? ")
               Then
                   ! User prays we can save the file. Well, here goes.
                   KeyFree=0 \ ! Set to something safe. This loses free space; tough.
                   Write #KeyChannel@KeyRootSize*(KeyNumber-1),...
&                        KeySize,KeyMaxKeyCount,KeyRoot,KeyFree
                   ! RESET FREE CHUNK LIST HERE
                   ! All places at or below Key Tree Root are busy.
                   If ChunkConflict(0,KeyRootSize*KeyNumber)
                   Then Print "Program Bug!"\Error 101 Fi
               Else Error BadKeyFile Fi
           Fi
           ! Find next free node
           Read #KeyChannel@KeyNodePointer,KeyNodePointer
       Unless KeyNodePointer=0 End
   Fi
!^L
   Print "Head of B-tree validated. Now visiting ALL Keys. Be patient."
   If KeyRoot=0
   Then
       Print "Empty B-Tree. Validation successful."\Exit
   Fi

   ! Now traverse the B-tree structure.
   ! At each node, perform the following tests:
   !    Reasonableness of KeyCount
   !    ChunkConflict on all sub-nodes of this node (including rightmost son)
   !    That order of Keys within node is ascending
   ! We traverse the tree top-down.  When we come down to a node,
   ! we first check its structure as outlined above.  Then we
   ! visit and validate all the sons, one by one, returning to a
   ! to find the next son and to verify that the next key contained in
   ! that node is larger than all the keys in the son just visited.
   !
   KeyNodePointer=KeyRoot \ ! Start traversal at root of tree
   KeyNodeStackLevel=0 \ ! Set stack of parent nodes to <empty>
   KeyMinKey$="" \ ! This is less than any possible key in the tree.
   len(KeyMaxKey$)=KeySize
   For i=1 to KeySize do KeyMaxKey$(i)=:FF \ ! Set up Maximum Key in subtree
   NextLeafNodePointer=0 \ ! Where next leaf node MUST be ("anywhere" code)
   TotalKeys=0 \ ! How many keys are actually in the file
   LeafNodeDepth=-1 \ ! Depth of all leaf nodes
   len(KeyTemp$)=KeySize
!^L
! *** Perhaps a Key-file Reorganize program might be a good idea.
! For F. B. and crew, the Key file builder could run while system in use.
! all they need to do is to put locks around the keyinsert, as usual.
! especially if they inserted the keys backwards: most 100 recent patients
! would be in the database in a minute or two.
ValidateKeyNode: ! Come here to visit B-tree node at KeyNodePointer
   ! Assert: KeyNodePointer is "reasonable", i.e., >0, integral,
   ! and far enough from end of file so that there is room for a key node
   ! Assert: KeyMinKey$ holds lowest possible key in subtree, -1 (unless 0)
   ! Assert: KeyMaxKey$ holds largest possible key in subtree.
   Read #KeyChannel@KeyNodePointer,KeyNodeKeyCount \ ! Get # keys in node
   If KeyNodeKeyCount<0
   Then
      ! This is a leaf node
100    Let KeyNodeKeyCount=-KeyNodeKeyCount
       If LeafNodeDepth=-1
       Then
           LeafNodeDepth=KeyNodeStackLevel \ ! remember depth of tree
           Print "B-tree depth: ";LeafNodeDepth+1;"(seeks per lookup)"
       ElseIf LeafNodeDepth<>KeyNodeStackLevel
       Then
           Print "Depth of leaf node at";KeyNodePointer;"is";KeyNodeStackLevel
           Print "Rest of tree has depth ";LeafNodeDepth
           Error BadKeyFile
       Fi
       If NextLeafNodePointer<>0 and NextLeafNodePointer<>KeyNodePointer
       Then
           Print "Leaf node next link inconsistent with location of leaf."
           Print "Node containing next link: ";PreviousLeafNodePointer
           Print "Where leaf should be: ";NextLeafNodePointer
           Print "Where leaf is: ";KeyNodePointer
           Error BadKeyFile
       Fi
       ! Validate number of keys in the node
       If KeyNodeKeyCount<>int(KeyNodeKeyCount) ...
&      Or KeyNodeKeyCount<int(KeyMaxKeyCount/2) ...
&                and KeyNodePointer<>KeyRoot ...
&      Or KeyNodeKeyCount>KeyMaxKeyCount
       Then
           Print "Bad Key Count (";KeyNodeKeyCount;...
&                ") in leaf node at";KeyNodePointer
           Error BadKeyFile
       Fi
       For KeySlot=1 to KeyNodeKeyCount
           TotalKeys=TotalKeys+1 \ ! Count existence of key.
110        Read #KeyChannel,KeyTemp,KeyTemp$[1,KeySize]
           !D! Print "LEAF:";KeyNodePointer;KeyTemp;">";KeyTemp$;"<" \ ! Show node scan
           ! We can do nothing to validate KeyTemp: it is application dependent
           ! Make sure each key is larger than the previous key
           ! Note: even if KeyTemp$=:00,:00,:00...,
           ! it will still be > KeyMinKey$ which is initz'd as EMPTY string
           If KeyTemp$<=KeyMinKey$
           Then
               Print "Keys out of order in leaf B-tree node at";KeyNodePointer
               Print "Prev Key >";KeyMinKey$;"<"
               Print "Bad Key  >";KeyTemp$;"<"
               Error BadKeyFile
           Fi
           If KeyTemp$>KeyMaxKey$
           Then
               Print "Key in leaf node at";KeyNodePointer;"exceeds max for node."
               Print "Min Key >";KeyMinKey$;"<"
               Print "Bad Key >";KeyTemp$;"<"
               Print "Max Key >";KeyMaxKey$;"<"
               Error BadKeyFile
           Fi
           KeyMinKey$=KeyTemp$ \ ! Remember next key must be larger than this
       Next KeySlot
       ! Process Right sibling pointer
120    Read #KeyChannel,NextLeafNode \ ! Determine location of next leaf
       If NextLeafNode<0 or NextLeafNode<>int(NextLeafNode) ...
&      or NextLeafNode+KeyNodeSize>FileSize
       Then
           Print "Bad Next Leaf node pointer in node ";KeyNodePointer
           Error BadKeyFile
       Fi
       PreviousLeafNodePointer=KeyNodePointer
       !
       ! Now return to scanning parent node.
       ! Note that KeyMinKey$ has been set to maximum key in this leaf node.
       Goto ScanNextParentKeySlot
   Else
200    ! This is an interior node
       ! Validate number of keys in the node
       If KeyNodeKeyCount<>int(KeyNodeKeyCount) ...
&      Or KeyNodeKeyCount<int(KeyMaxKeyCount/2) ...
&                and KeyNodePointer<>KeyRoot ...
&      Or KeyNodeKeyCount>KeyMaxKeyCount
       Then
           Print "Bad Key Count (";KeyNodeKeyCount;...
&                ") in interior node at";KeyNodePointer
           Error BadKeyFile
       Fi
       ! When we first arrive at a node, we record all relevant details in
       ! KeyNodeStackXXXX(i), so that we can locate a node's father after
       ! visiting the node and continue processing the father where we left off.
       !
       KeyNodeStackLevel=KeyNodeStackLevel+1 \ ! Add a new level to the stack
       KeyNodeStackAddress(KeyNodeStackLevel)=KeyNodePointer \ ! Where node is
       KeyNodeStackKeyCount(KeyNodeStackLevel)=KeyNodeKeyCount \ ! # Keys in node
       KeyNodeStackNextKey(KeyNodeStackLevel)=0 \ ! # Keys processed
       KeyNodeStackMaxKey$(KeyNodeStackLevel)=KeyMaxKey$ \ ! remember Max key
       !
       ! Validate the contents of this B-tree node before visiting sons
       !
       KeyPrevious$=KeyMinKey$ \ ! Start with least possible key in node
       For KeySlot=0 to KeyNodeKeyCount-1
210        Read #KeyChannel,KeyTemp,KeyTemp$[1,KeySize]
           !D! Print "INTERIOR:";KeyNodePointer;KeyTemp;">";KeyTemp$;"<" \ ! Show node scan
           If ChunkConflict(KeyTemp,KeyNodeSize)
           Then
               Print "Overlapping B-tree node at";KeyTemp;...
&                    "under";KeyNodePointer
               Error BadKeyFile
           Fi
           If KeyTemp$<=KeyPrevious$
           Then
               Print "Keys out of order in interior B-tree node at";KeyNodePointer
               Print "Prev Key >";KeyPrevious$;"<"
               Print "Bad Key  >";KeyTemp$;"<"
               Print "Max Key  >";KeyMaxKey$;"<"
               Error BadKeyFile
           Fi
           If KeyTemp$>KeyMaxKey$
           Then
               Print "Key in interior node at";KeyNodePointer;"exceeds max for node."
               Print "Min Key >";KeyMinKey$;"<"
               Print "Bad Key >";KeyTemp$;"<"
               Print "Max Key >";KeyMaxKey$;"<"
               Error BadKeyFile
           Fi
           KeyPrevious$=KeyTemp$
       Next KeySlot
       ! Process Rightmost son pointer
       If ChunkConflict(KeyTemp,KeyNodeSize)
       Then
           Print "Overlapping B-tree node at";KeyTemp;...
&                "under";KeyNodePointer
           Error BadKeyFile
       Fi
220    ! Now visit sons of this node and validate them, recursively.
       ! (BASIC isn't recursive, so we fake it)
       ! Start with 1st son.
       !D! Print "KeyNodeStackAddress=";KeyNodeStackAddress(KeyNodeStackLevel)
       !D! Print "KeyNodeStackNextKey=";KeyNodeStackNextKey(KeyNodeStackLevel)
       Read #KeyChannel@KeyPointerPair(KeyNodeStackAddress(KeyNodeStackLevel),...
&                                      KeyNodeStackNextKey(KeyNodeStackLevel)),...
&                       KeyNodePointer,KeyMaxKey$[1,KeySize]
       !D! Print "1st son at";KeyNodePointer;"Max Key>";KeyMaxKey$;"<"
       Goto ValidateKeyNode \ ! Go validate 1st son, come back to ScanNext...
   Fi
!^L
ScanNextParentKeySlot:
300 ! dummy line for tracing purposes
   KeyNodeStackNextKey(KeyNodeStackLevel)=...
&         KeyNodeStackNextKey(KeyNodeStackLevel)+1 \ ! bump # keys processed
   If KeyNodeStackNextKey(KeyNodeStackLevel) ...
&     < KeyNodeStackKeyCount(KeyNodeStackLevel)
   Then
       ! Another (ptr,key) pair still needs to be processed.
       Read #KeyChannel@KeyPointerPair(KeyNodeStackAddress(KeyNodeStackLevel),...
&                                      KeyNodeStackNextKey(KeyNodeStackLevel)),...
&                       KeyNodePointer,KeyMaxKey$[1,KeySize]
       Goto ValidateKeyNode \ ! Go validate son, come back to ScanNext...
   ElseIf KeyNodeStackNextKey(KeyNodeStackLevel) ...
&         = KeyNodeStackKeyCount(KeyNodeStackLevel)
   Then
       ! All sons except the rightmost have been processed.
       ! Locate the rightmost son.
       ! Not through processing this node yet.
       Read #KeyChannel@KeyPointerPair(KeyNodeStackAddress(KeyNodeStackLevel),...
&                                      KeyNodeStackNextKey(KeyNodeStackLevel)),...
&                       KeyNodePointer
       KeyMaxKey$=KeyNodeStackMaxKey$[KeyNodeStackLevel]
       Goto ValidateKeyNode \ ! Go validate son, come back to ScanNext...
   Else
       ! All sons of this node have been processed.
       ! Find parent by popping stack.
       KeyNodeStackLevel=KeyNodeStackLevel-1 \ ! Pop stack
       !D! Print "Popping stack to level";KeyNodeStackLevel
       ! Go finish parent if stack is not empty.
       If KeyNodeStackLevel>0 Then ScanNextParentKeySlot Fi
   Fi
   Print "Key Validation completed. No errors found."
   Print "Total keys in B-tree: ";TotalKeys
   Exit

END
!^L
!
! KEY DATA STRUCTURES:
!
! KEY FILE STRUCTURE:
!        KEY-TREE ROOT NODE
!        KEY-TREE ROOT NODE
!        ...
!        KEY-TREE ROOT NODE
!        OPTIONAL DATA RECORDS
!
! KEY-TREE ROOT NODE:
!        KEYSIZE(6 BYTES)
!        MAXKEYCOUNT(6 BYTES)
!        POINTER (TO ROOT B-TREE NODE; MAY BE NULL (=0))
!        POINTER TO AVAILABLE B-TREE NODE LIST FOR THIS TREE
!
! B-TREE NODE: (SEE STANDISH, "DATA STRUCTURES")
!        KEYCOUNT (AT THIS NODE) SUCHTHAT KEYCOUNT<=MAXKEYCOUNT
!            IF INTERIOR TREE NODE, KEYCOUNT IS ABS(TRUEKEYCOUNT)
!            IF LEAF NODE, KEYCOUNT IS -ABS(TRUEKEYCOUNT)
!        POINTERKEYPAIR[1..KEYCOUNT]
!        RIGHT SON/ RIGHT SIBLING POINTER
!
!        NOTE: B-TREE NODES COME IN TWO FLAVORS: INTERIOR AND LEAF
!        AN INTERIOR NODE CONTAINS ONLY POINTERS TO "SON" NODES
!            THE RIGHTMOST "SON" POINTER POINTS TO A NODE WHOSE KEYS
!            ARE ALL GREATER THAN ALL KEYS CONTAINED IN THE FATHER NODE
!        A LEAF NODE CONTAINS POINTERS TO RECORDS; THE RIGHT "SON" POINTER...
!            POINTS TO THE LEAF NODE CONTAINING THE NEXT LOGICAL KEY
!            (I.E., IS USED AS A RIGHT "SIBLING" POINTER)
!        ALSO NOTE THAT B-TREE NODES MUST STAY AT LEAST HALF FULL
!            TO MAKE SEARCH TIMES EFFICIENT. "HALF-FULL" FOR AN
!            INTERIOR NODE MEANS THAT IT HAS AT LEAST INT(MAXKEYCOUNT+1)/2 SONS
!            "HALF-FULL" FOR A LEAF NODE MEANS IT HAS AT LEAST
!            INT(MAXKEYCOUNT/2) KEYS. THIS DIFFERENCE IS CRUCIAL!
!
! POINTERKEYPAIR:
!        POINTER (TO SON WITH KEYS <= KEY1$)
!        KEY1$(KEYSIZE BYTES) (NOTE: MUST BE KEY CURRENTLY IN TREE)
!
! POINTER: (6 BYTES; = BASIC FORMAT NUMBER)
!        >0 --> POINTS TO B-TREE NODE
!        <0 --> POINTS TO RECORD
!        =0 --> NO MORE RIGHT SIBLINGS (0 NOT ALLOWED IN INTERIOR NODES)
