REM THIS PROGRAM CONTAINS A KEY FILE PACKAGE BASED UPON B-TREES
REM IT IMPLEMENTS THE SD KEY FILE PACKAGE (KEY.BAS)
REM THIS FILE SHOULD BE "INCLUDE"D IN THE SOURCE OF THE APPLICATION

REM REVISION HISTORY:
REM 3/24/81 KEY10A.BAS: FIRST IMPLEMENTATION
REM 3/24/85 KEY10B.BAS: IDB MODIFICATIONS TO OPERATE CORRECTLY IN SDOS/MT ENVIRONMENT
REM         KILLED KEYNEXTOPTIMIZEOK LOGIC
REM         FORCED KEYSETUP TO ALWAYS READ B-TREE HEAD FROM FILE
REM         WARNING: USE UNDER SDOS/MT REQUIRES KEYED ACCESSES TO BE LOCKED!
REM 1/11/88 KEY10C.BAS: RE-INSTALLED KEYNEXTOPTIMIZE USING FILE DATE STAMPS
REM         RENAMED VARIABLE "KEY$" TO "KEYDESIRED$" SO APPLICATION PROGRAMS
REM         CAN USED "KEY$" WITHOUT PROBLEMS.

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

REM THE FOLLOWING DATA IS EXTRACTED FROM FILE BEFORE KEY ROUTINES DO ANY WORK
DIM KEYROOTSIZE/24/,KEYSIZE,KEYMAXKEYCOUNT,KEYROOT,KEYFREE

REM THE FOLLOWING DATA ARE USED TO KEEP TRACK OF THE SOURCE OF THE ROOT DATA
DIM KEYCHANNEL/-1/,KEYNUMBER/-1/,KEYSUNLOCKED/0/

REM THE FOLLOWING ARE USED TO KEEP TRACK OF WHETHER IT IS SAFE TO OPTIMIZE KEYNEXT CALLS
DIM KEYNEXTOPTIMIZEOK/0/,KEYDESIRED$[64],KEYDATESTAMP$/0,0,0,0,0,0/

REM THE FOLLOWING ARE USED TO OPTIMIZE KEYNEXT WHEN IT IS SAFE TO DO SO
REM KEYNODEPOINTER,KEYNODEKEYCOUNT,KEYSLOT

REM THE FOLLOWING DATA IS SCRATCH STUFF
DIM KEYTEMP$[64],KEYMIDKEY$[64]

REM THE FOLLOWING ARE CONSTANTS USED FREQUENTLY BY THE KEY PACKAGE
DIM KEYZEROS$/:0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0/
DIM KEYSCGETFILEDATE$/:F,14,0,:10/,KEYSCGETFILESIZE$/:F,14,0,:3/

DEF FILESIZE(FILESIZECHANNEL)
    REM RETURNS SIZE OF FILE OPENED ON "CHANNEL"
    DIM FILESIZETEMP$(4)
    SYSCALL #FILESIZECHANNEL,KEYSCGETFILESIZE$,"",FILESIZETEMP$
    RETURN FILESIZETEMP$[1]*256^3+FILESIZETEMP$[2]*256^2 ...
&          +FILESIZETEMP$[3]*256+FILESIZETEMP$[4]
END

DEF GETSPACE(GETSPACECHANNEL,HOWMUCHSPACETOGET)
    DIM KEYDUMMYBYTE$/0/
    REM THIS FUNCTION FINDS FREE SPACE IN A FILE (BY GOING TO EOF)
    REM IT EXTENDS THE FILE BY "HOWMUCHSPACETOGET"
    REM AND RETURNS THE LOCATION OF THE SPACE ALLOCATED
    LET ALLOCATEDSPACE=FILESIZE(GETSPACECHANNEL)
    WRITE #GETSPACECHANNEL@ALLOCATEDSPACE+HOWMUCHSPACETOGET-1,KEYDUMMYBYTE$
    RETURN ALLOCATEDSPACE
END
!^L
SUBROUTINE KEYINIT(KEYINITCHANNEL,KEYINITKEYNUMBER,...
&                    KEYINITSIZEINBYTES,KEYINITMAXKEYCOUNT)
    REM THIS SUBROUTINE INITIALIZES A KEY STRUCTURE IN A FILE
    IF KEYINITSIZEINBYTES>MAXLEN(KEYDESIRED$) THEN ERROR 11
    REM KEYDELETE REQUIRES 2 KEYS/NODE, MIN --> 4 KEYS/MAX AS MINIMUM!
    IF KEYINITMAXKEYCOUNT<4 THEN ERROR 1077
    KEYCHANNEL=KEYINITCHANNEL
    KEYNUMBER=KEYINITKEYNUMBER
    KEYSIZE=KEYINITSIZEINBYTES
    KEYMAXKEYCOUNT=KEYINITMAXKEYCOUNT
    KEYROOT=0
    KEYFREE=0
    CALL KEYUPDATE \ ! MAKE SURE THE FILE GETS THIS INFORMATION
    RETURN SUBROUTINE
END

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

DEF KEYGETNEWNODE
    REM GET A NEW NODE FOR USE BY THE KEYED FILE PACKAGE
    REM IF A NODE IS CURRENTLY ON THE FREE LIST, RE-USE IT
    REM OTHERWISE GET NEW SPACE AT <EOF>
    REM THIS SUBROUTINE IS USED INTERNALLY BY KEYINSERT
    IF KEYFREE<>0
    THEN
        REM USE FIRST NODE ON FREE CHAIN AS RESULT
        LET KEYNODEOBTAINED=KEYFREE
        REM REMOVE FIRST NODE OF FREE CHAIN FROM THE CHAIN
        READ #KEYCHANNEL@KEYFREE,KEYFREE
        CALL KEYUPDATE \ ! MAKE SURE TREE HEADER IS UPDATED
        RETURN KEYNODEOBTAINED
    ELSE RETURN GETSPACE(KEYCHANNEL,12+KEYMAXKEYCOUNT*(KEYSIZE+6))
END
!^L
SUBROUTINE KEYSETUP(KEYSETUPCHANNEL,KEYSETUPKEYNUMBER,KEYSETUPKEY$)
    KEYNEXTOPTIMIZEOK=FALSE \ ! PREVENT KEYNEXT FROM OPTIMIZING
    REM SKIP EXTRA DISK READ IF LAST KEY CALL USED SAME CHANNEL, KEYNUMBER
    IF KEYCHANNEL<>KEYSETUPCHANNEL OR KEYNUMBER<>KEYSETUPKEYNUMBER
    THEN
        REM CANNOT AVOID READING HEAD OF B-TREE
        KEYCHANNEL=KEYSETUPCHANNEL
        KEYNUMBER=KEYSETUPKEYNUMBER
        READ #KEYCHANNEL@KEYROOTSIZE*(KEYNUMBER-1),...
&            KEYSIZE,KEYMAXKEYCOUNT,KEYROOT,KEYFREE
        SYSCALL #KEYSETUPCHANNEL,KEYSCGETFILEDATE$,"",KEYDATESTAMP$
                ! Record date stamp for use later in test below.
    ELSE
        ! Perhaps we can avoid re-reading heading of B-tree.
!       IF KEYSUNLOCKED
!       THEN
            ! This user allowed some other user to potentially update key file.
!           KEYSUNLOCKED=false \ ! Assert: keys *are* locked here.
            ! If User program doesn't share key file, then it can ignore KEYSUNLOCKED.
            ! Otherwise, user program *MUST* do 'KEYSUNLOCKED=true' when unlocking keys.
            ! Check to see if file date has changed since last reference.
            SYSCALL #KEYSETUPCHANNEL,KEYSCGETFILEDATE$,"",KEYTEMP$
            IF KEYTEMP$<>KEYDATESTAMP$
            THEN
                ! Timestamp has changed, --> file content has changed.
                ! (SDOS gaurantees that timestamp changes when file does)
                ! --> We must re-read head of B-TREE because it might have changed
                ! But a large disk buffer pool will help keep the cost down.
                KEYDATESTAMP$=KEYTEMP$ \ ! Remember file date stamp, too.
                KEYCHANNEL=KEYSETUPCHANNEL
                KEYNUMBER=KEYSETUPKEYNUMBER
                READ #KEYCHANNEL@KEYROOTSIZE*(KEYNUMBER-1),...
&                    KEYSIZE,KEYMAXKEYCOUNT,KEYROOT,KEYFREE
            FI
!       FI
    FI
    ! SET KEYDESIRED$ TO NULL FILLED VERSION OF KEYINSERTKEY$, EFFICIENTLY.
    LET LEN(KEYDESIRED$)=KEYSIZE
    LET KEYDESIRED$[1,KEYSIZE]=KEYSETUPKEY$
    FOR KEYINDEX=LEN(KEYSETUPKEY$)+1 TO KEYSIZE STEP LEN(KEYZEROS$)
        LET RIGHT$(KEYDESIRED$,KEYINDEX)=KEYZEROS$
    NEXT KEYINDEX
    LET LEN(KEYTEMP$)=KEYSIZE
    LET LEN(KEYMIDKEY$)=KEYSIZE
    LET KEYNODEPOINTER=KEYROOT
    EXIT SUBROUTINE
END

SUBROUTINE KEYUPDATE
REM THIS SUBROUTINE IS USED TO FORCE UPDATE OF A KEY FILE
REM IT IS USED INTERNALLY IN THE KEY FILE PACKAGE
    WRITE #KEYCHANNEL@KEYROOTSIZE*(KEYNUMBER-1),...
&         KEYSIZE,KEYMAXKEYCOUNT,KEYROOT,KEYFREE
    RETURN SUBROUTINE
END
!^L
SUBROUTINE KEYINSERT(KEYINSERTCHANNEL,KEYINSERTKEYNUMBER,...
&                    KEYINSERTKEY$,KEYINSERTVALUE)
REM THIS SUBROUTINE IS USED TO INSERT A NEW KEY RECORD INTO THE FILE.
REM USE FORMAT: LET RECORDLOC=...
REM             WRITE #DATAFILE@RECORDLOC,recordcontents
REM             CALL KEYINSERT(KEYFILE,KEYNUMBER,KEY$,RECORDLOC)
REM             If the record has more than one key, multiple CALLs are needed
    CALL KEYSETUP(KEYINSERTCHANNEL,KEYINSERTKEYNUMBER,KEYINSERTKEY$)
    REM AT TOP OF TREE IS VERY SPECIAL CASE
    IF KEYROOT=0
    THEN
        REM EMPTY TREE, INVENT A B-TREE NODE FOR FIRST TREE LEVEL
        LET KEYNODEPOINTER=KEYGETNEWNODE
        LET KEYROOT=KEYNODEPOINTER
        CALL KEYUPDATE \ ! MAKE SURE THIS GETS BACK TO FILE
        REM SPECIAL CASE, WRITE COMPLETE B-TREE FOR 1ST INSERT, + "EOF" PTR
        WRITE #KEYCHANNEL@KEYNODEPOINTER,-1,KEYINSERTVALUE,KEYDESIRED$,0
        RETURN SUBROUTINE
    FI
KEYINSERTEXAMINESONNODE:
    READ #KEYCHANNEL@KEYNODEPOINTER,KEYNODEKEYCOUNT
    IF KEYNODEKEYCOUNT>=0
    THEN
        REM THIS IS AN INTERIOR NODE
        LET KEYINTERIORNODEFLAG=TRUE
    ELSE
        REM THIS IS A LEAF NODE
        LET KEYINTERIORNODEFLAG=FALSE
        LET KEYNODEKEYCOUNT=-KEYNODEKEYCOUNT
    FI
    REM SPLIT A B-TREE NODE ON WAY DOWN TREE IF IT IS COMPLETELY FULL
    IF KEYNODEKEYCOUNT=KEYMAXKEYCOUNT
    THEN
        REM THIS NODE IS FULL, WE MUST SPLIT IT INTO TWO
        REM NODE ABOVE US CANNOT BE FULL, BECAUSE IF IT WAS, IT JUST GOT SPLIT
        REM ALLOCATE NEW B-TREE NODE
        LET KEYNEWNODEPOINTER=KEYGETNEWNODE
        REM COMPUTE NEW KEY COUNTS FOR NODE BEING SPLIT, AND NEW BROTHER NODE
        LET KEYNODEKEYCOUNT=...
&           INT((KEYMAXKEYCOUNT+1-KEYINTERIORNODEFLAG)/2)
        LET KEYNEWNODEKEYCOUNT=...
&           KEYMAXKEYCOUNT-KEYNODEKEYCOUNT-KEYINTERIORNODEFLAG
        REM FIX UP HEADERS OF B-TREE NODES RESULTING FROM SPLIT
        IF KEYINTERIORNODEFLAG
        THEN
            REM INTERIOR NODES HAVE POSITIVE KEY COUNTS
            WRITE #KEYCHANNEL@KEYNODEPOINTER,KEYNODEKEYCOUNT
            WRITE #KEYCHANNEL@KEYNEWNODEPOINTER,KEYNEWNODEKEYCOUNT
        ELSE
            REM LEAF NODES HAVE NEGATIVE KEY COUNTS
            WRITE #KEYCHANNEL@KEYNODEPOINTER,-KEYNODEKEYCOUNT
            WRITE #KEYCHANNEL@KEYNEWNODEPOINTER,-KEYNEWNODEKEYCOUNT
        FI
        REM COPY RIGHT HALF OF B-TREE NODE TO LEFT HALF OF NEWLY ALLOCATED NODE
        REM IF INTERIOR NODE, MIDDLE KEY IS MOVED UP TO PARENT
        REM IF LEAF NODE, MIDDLE KEY KEPT BY OLD NODE, AND MOVED UP TO PARENT
        FOR KEYINDEX=0 TO KEYNEWNODEKEYCOUNT-1
            REM THE ...+KEYINTERIORNODEFLAG+... FOLLOWING
            REM IS SO WE DON'T COPY THE MIDDLE KEY IF THIS IS AN INTERIOR NODE
            READ #KEYCHANNEL...
&                @KEYPOINTERPAIR(KEYNODEPOINTER,...
&                                KEYNODEKEYCOUNT+KEYINTERIORNODEFLAG...
&                                                      +KEYINDEX),...
&                KEYTEMP,KEYTEMP$[1,KEYSIZE]
            WRITE #KEYCHANNEL...
&                 @KEYPOINTERPAIR(KEYNEWNODEPOINTER,KEYINDEX),...
&                 KEYTEMP,KEYTEMP$
        NEXT KEYINDEX
        REM COPY RIGHTMOST SON POINTER OF SPLIT NODE TO NEWLY ALLOCATED NODE
        READ #KEYCHANNEL...
&            @KEYPOINTERPAIR(KEYNODEPOINTER,...
&                            KEYNODEKEYCOUNT+KEYINTERIORNODEFLAG...
&                                                  +KEYINDEX),...
&            KEYTEMP
        WRITE #KEYCHANNEL@KEYPOINTERPAIR(KEYNEWNODEPOINTER,KEYINDEX),...
&             KEYTEMP
        REM READ MIDDLE KEY OUT OF SPLIT NODE
        READ #KEYCHANNEL...
&            @KEYPOINTERPAIR(KEYNODEPOINTER,...
&                            KEYNODEKEYCOUNT-1+KEYINTERIORNODEFLAG)+6,...
&            KEYMIDKEY$[1,KEYSIZE]
        REM IF LEAF NODE, MAKE RIGHTMOST SON = POINTER TO SIBLING NODE
        IF NOT KEYINTERIORNODEFLAG
        THEN WRITE #KEYCHANNEL...
&                  @KEYPOINTERPAIR(KEYNODEPOINTER,KEYNODEKEYCOUNT),...
&                  KEYNEWNODEPOINTER
        REM CHOOSE WHICH SON TO SEARCH AFTER PARENT IS UPDATED
        KEYSONTOSEARCH=IF KEYDESIRED$<=KEYMIDKEY$
                       THEN KEYNODEPOINTER ELSE KEYNEWNODEPOINTER FI
        REM NOW INSERT MIDDLE KEY IN PARENT NODE
        IF KEYNODEPOINTER=KEYROOT
        THEN
            REM WE JUST SPLIT THE NODE AT THE TOP OF THE TREE
            REM INVENT A NEW PARENT NODE
            LET KEYPARENT=KEYGETNEWNODE
            LET KEYPARENTKEYCOUNT=0
            LET KEYSLOT=0 \ ! INSERTION POINT IN PARENT
            REM SET UP POINTER IN PARENT NODE TO SON BEING SPLIT
            WRITE #KEYCHANNEL@KEYPARENT+6,KEYNODEPOINTER
            LET KEYROOT=KEYPARENT
            CALL KEYUPDATE \ ! MAKE SURE THIS GETS TO FILE
            REM NOW REST OF PROCESS IS IDENTICAL!
        FI
        REM COPY MIDDLE KEY FROM SPLIT NODE TO PARENT
        REM ASSERT: 0<=KEYSLOT<=KEYPARENTKEYCOUNT
        REM PLANT (MIDDLEKEY,POINTERTONEWNODE)
        REM AND SHUFFLE PARENT DATA RIGHT TO MAKE ROOM
        LET KEYTEMP2=KEYNEWNODEPOINTER
        FOR KEYPARENTSCAN=KEYSLOT TO KEYPARENTKEYCOUNT-1
            REM MAKE ROOM TO SHUFFLE RIGHT BY READING NEXT KEYPOINTERPAIR
            READ #KEYCHANNEL@KEYPOINTERPAIR(KEYPARENT,KEYPARENTSCAN)+6,...
&                KEYTEMP$[1,KEYSIZE],KEYTEMP
            REM NOW ROOM IS MADE, FILL NEXT SLOT WITH THIS KEYPOINTER PAIR
            WRITE #KEYCHANNEL@KEYPOINTERPAIR(KEYPARENT,KEYPARENTSCAN)+6,...
&                KEYMIDKEY$,KEYTEMP2
            REM MAKE NEXT KEYPOINTERPAIR INTO THIS KEYPOINTERPAIR
            KEYMIDKEY$=KEYTEMP$
            KEYTEMP2=KEYTEMP
        NEXT KEYPARENTSCAN
        REM FINISH SHUFFLE RIGHT
        WRITE #KEYCHANNEL@KEYPOINTERPAIR(KEYPARENT,KEYPARENTSCAN)+6,...
&             KEYMIDKEY$,KEYTEMP2
        REM BUMP BRANCHING FACTOR IN PARENT NODE
        WRITE #KEYCHANNEL@KEYPARENT,KEYPARENTKEYCOUNT+1
        REM NOW SET UP TO SEARCH PROPER SON NODE
        KEYNODEPOINTER=KEYSONTOSEARCH
        GOTO KEYINSERTEXAMINESONNODE
    FI \ REM AND THAT TAKES CARE OF SPLITTING A NODE!

    REM NOW SEARCH SON NODE FOR PLACE TO INSERT KEYDESIRED$
    REM ASSERT: WE ARE POSITIONED @KEYPOINTERPAIR(KEYNODEPOINTER,0)
    FOR KEYSLOT=0 TO KEYNODEKEYCOUNT-1
        READ #KEYCHANNEL,KEYTEMP,KEYTEMP$[1,KEYSIZE]
        IF KEYDESIRED$<=KEYTEMP$
        THEN IF KEYINTERIORNODEFLAG
             THEN
                 KEYPARENT=KEYNODEPOINTER \ ! HONOR THY PARENTS
                 KEYPARENTKEYCOUNT=KEYNODEKEYCOUNT
                 KEYNODEPOINTER=KEYTEMP
                 GOTO KEYINSERTEXAMINESONNODE
             ELSE IF KEYDESIRED$=KEYTEMP$
                  THEN ERROR 1076 \ ! DUPLICATE KEY SPECIFIED
                  ELSE KEYINSERTPOINTFOUND
    NEXT KEYSLOT
    REM ASSERT KEYDESIRED$ > THAN ALL KEYS IN THIS NODE
    IF KEYINTERIORNODEFLAG
    THEN
        REM NOT A LEAF NODE, RIGHTMOST SON POINTER IS PLACE TO GO!
        KEYPARENT=KEYNODEPOINTER \ ! HONOR THY PARENTS
        KEYPARENTKEYCOUNT=KEYNODEKEYCOUNT
        READ #KEYCHANNEL,KEYNODEPOINTER
        GOTO KEYINSERTEXAMINESONNODE
    FI
    REM ELSE IS LEAF NODE, ADD KEYDESIRED$ TO RIGHT END OF NODE!
KEYINSERTPOINTFOUND: REM KEYSLOT <= KEYNODEKEYCOUNT
    REM PLANT (KEYDESIRED$,KEYINSERTVALUE) AND...
    REM SHUFFLE REST OF B-TREE LEAF DATA RIGHT TO MAKE ROOM
    LET KEYTEMP=KEYINSERTVALUE
    FOR KEYSLOT=KEYSLOT TO KEYNODEKEYCOUNT
        READ #KEYCHANNEL@KEYPOINTERPAIR(KEYNODEPOINTER,KEYSLOT),...
&            KEYTEMP2,KEYTEMP$[1,KEYSIZE]
        WRITE #KEYCHANNEL@KEYPOINTERPAIR(KEYNODEPOINTER,KEYSLOT),...
&             KEYTEMP,KEYDESIRED$
        KEYTEMP=KEYTEMP2
        KEYDESIRED$=KEYTEMP$
    NEXT KEYSLOT
    REM MOVE RIGHT SIBLING POINTER OVER
    WRITE #KEYCHANNEL,KEYTEMP2
    REM LAST, BUT NOT LEAST! BUMP BRANCHING FACTOR IN THIS NODE
    WRITE #KEYCHANNEL@KEYNODEPOINTER,-(KEYNODEKEYCOUNT+1)
    RETURN SUBROUTINE \ REM INSERT IS COMPLETE
END
!^L
DEF KEY(KEYKEYCHANNEL,KEYKEYNUMBER,KEYKEY$)
REM THIS FUNCTION IS USED TO LOCATE A KEY RECORD IN A FILE.
REM USE FORMAT: READ #M@KEY(N,K,KEY$),TARGET,....
REM OPERATION IS ALMOST IDENTICAL TO "KEYNEXT" SO KEYNEXT CAN OPTIMIZE
    CALL KEYSETUP(KEYKEYCHANNEL,KEYKEYNUMBER,KEYKEY$)
    IF KEYROOT=0 THEN ERROR 1075 \ ! EMPTY TREE --> NO SUCH KEY
KEYSEARCHSONNODE:
    READ #KEYCHANNEL@KEYNODEPOINTER,KEYNODEKEYCOUNT
    IF KEYNODEKEYCOUNT>=0
    THEN
        REM THIS IS AN INTERIOR NODE
        LET KEYINTERIORNODEFLAG=TRUE
    ELSE
        REM THIS IS A LEAF NODE
        LET KEYINTERIORNODEFLAG=FALSE
        LET KEYNODEKEYCOUNT=-KEYNODEKEYCOUNT
    FI
    FOR KEYSLOT=0 TO KEYNODEKEYCOUNT-1
        READ #KEYCHANNEL,KEYTEMP,KEYTEMP$[1,KEYSIZE]
        IF KEYDESIRED$<=KEYTEMP$
        THEN IF KEYINTERIORNODEFLAG
             THEN
                 LET KEYNODEPOINTER=KEYTEMP
                 GOTO KEYSEARCHSONNODE
             ELSE IF KEYDESIRED$=KEYTEMP$
                  THEN
                      KEYNEXTOPTIMIZEOK=TRUE \ ! SAFE TO OPTIMIZE NEXT KEYNEXT
                      RETURN KEYTEMP
                  ELSE ERROR 1075 \ ! AT LEAF, CAN'T FIND KEY --> NO SUCH KEY
    NEXT KEYSLOT
    REM CAN ONLY GET HERE IF KEYDESIRED$ IS > THAN ALL KEYS IN NODE
    IF KEYINTERIORNODEFLAG
    THEN
        REM THIS IS AN INTERIOR NODE, THE RIGHT LINK POINTS TO SON
        READ #KEYCHANNEL,KEYNODEPOINTER
        GOTO KEYSEARCHSONNODE
    ELSE
        REM THIS NODE IS A LEAF, THE DESIRED KEY DOES NOT EXIST
        ERROR 1075 \ ! NO SUCH KEY
    FI
END

DEF KEYREPLACE(KEYREPLACECHANNEL,KEYREPLACEKEYNUMBER,...
&              KEYREPLACEKEY$,KEYREPLACEVALUE)
REM THIS FUNCTION IS USED TO REPLACE THE VALUE OF A KEY
REM IT IS SIGNIFICANTLY FASTER THAN ...KEYDELETE...KEYINSERT
REM TO OBTAIN THE SAME EFFECT.
REM THE SPECIFIED KEY MUST EXIST OR AN ERROR WILL RESULT
    REM CALL KEY TO LOCATE THE DESIRED POINT IN THE LEAF NODE
    KEYTEMP=KEY(KEYREPLACECHANNEL,KEYREPLACEKEYNUMBER,KEYREPLACEKEY$)
    REM NOW UPDATE THE VALUE OF THE KEY
    WRITE #KEYCHANNEL@KEYPOINTERPAIR(KEYNODEPOINTER,KEYSLOT),KEYREPLACEVALUE
    REM AND RETURN THE ORIGINAL VALUE OF THE KEY
    RETURN KEYTEMP
END
!^L
DEF KEYNEXT(KEYNEXTCHANNEL,KEYNEXTKEYNUMBER,KEYNEXTKEY$)
REM THIS FUNCTION IS USED TO READ THE KEY AND THE RECORD CONTENTS OF
REM THE RECORD WHOSE KEY FOLLOWS THAT OF KEYNEXTKEY$ IN ALPHABETIC ORDER.
REM USE FORMAT: READ #DATAFILE@KEYNEXT(KEYFILE,KEYINDEX,KEY$),TARGET...
REM AN EOF ERROR IS SIGNALED IF NO FURTHER RECORDS EXIST.
REM KEY$ IS UPDATED TO CONTAIN THE NEXT KEY
REM **** WARNING: IT IS ILLEGAL TO CALL KEYNEXT WITH A CONSTANT STRING ARG ****
REM IF KEYNEXT IS CALLED SEQUENTIALLY, AN OPTIMIZED TREE SCAN IS PERFORMED
    REM CHECK FOR POSSIBLE TO OPTIMIZE
    IF KEYCHANNEL=KEYNEXTCHANNEL AND KEYNUMBER=KEYNEXTKEYNUMBER...
&      AND KEYNEXTOPTIMIZEOK AND KEYDESIRED$=KEYNEXTKEY$
    THEN
        REM NTH SEQUENTIAL CALL TO "KEYNEXT":
        ! Perhaps we can pick up processing where we left off last.
        ! This makes for very fast KEYNEXTs because of leaf chains.
!       IF KEYSUNLOCKED
!       THEN
            ! This user allowed some other user to potentially update key file.
!           KEYSUNLOCKED=false \ ! Assert: keys *are* locked here.
            ! Check to see if file date has changed since last reference.
            SYSCALL #KEYSETUPCHANNEL,KEYSCGETFILEDATE$,"",KEYTEMP$
            ! If timestamp has changed, --> file content has changed.
            ! (SDOS gaurantees that timestamp changes when file does)
            ! --> We must traverse B-tree from top again in case it changed.
            ! But a large disk buffer pool will help keep the cost down
            IF KEYTEMP$<>KEYDATESTAMP$
            THEN KEYNEXTHARDWAY FI \ ! This will force resync of KEYDATESTAMP$
            ! Timestamp has *NOT* changed --> file has not changed.
!           ! No other user could have modified the file.
!       FI
        ! PICK UP TREE PROCESSING WHERE WE LEFT OFF
        LET KEYFIRST=KEYSLOT+1 \ ! KEYSLOT "POINTS" TO KEYDESIRED$, ADVANCE PAST IT
        POSITION #KEYCHANNEL@KEYPOINTERPAIR(KEYNODEPOINTER,KEYFIRST)
        KEYNEXTOPTIMIZEOK=FALSE \ ! IN CASE KEYNEXT DOESN'T SUCCEED
        ! assert: KEYINTERIORNODEFLAG=false.
        LEN(KEYTEMP$)=KEYSIZE
        GOTO KEYNEXTOPTIMIZED
    FI
!^L
KEYNEXTHARDWAY: REM IT IS NOT POSSIBLE TO OPTIMIZE, DO IT THE HARD WAY!
    CALL KEYSETUP(KEYNEXTCHANNEL,KEYNEXTKEYNUMBER,KEYNEXTKEY$)
    REM CHECK FOR EMPTY TREE, AND EXIT IF SO...
    IF KEYROOT=0 THEN ERROR 1001 \ ! NO MORE KEYS --> EOF
KEYNEXTSEARCHSONNODE:
    KEYFIRST=0
    READ #KEYCHANNEL@KEYNODEPOINTER,KEYNODEKEYCOUNT
    IF KEYNODEKEYCOUNT>=0
    THEN
        REM THIS IS AN INTERIOR NODE
        LET KEYINTERIORNODEFLAG=TRUE
    ELSE
        REM THIS IS A LEAF NODE
        LET KEYINTERIORNODEFLAG=FALSE
        LET KEYNODEKEYCOUNT=-KEYNODEKEYCOUNT
    FI
KEYNEXTOPTIMIZED:
    FOR KEYSLOT=KEYFIRST TO KEYNODEKEYCOUNT-1
        READ #KEYCHANNEL,KEYTEMP,KEYTEMP$[1,KEYSIZE]
        IF KEYDESIRED$<KEYTEMP$
        THEN IF KEYINTERIORNODEFLAG
             THEN
                 KEYNODEPOINTER=KEYTEMP
                 GOTO KEYNEXTSEARCHSONNODE
             ELSE
                 REM AT DESIRED POINT IN LEAF NODE.
                 REM SAVE CURRENT STATE IN CASE KEYNEXT CALLED AGAIN
                 REM CURRENT STATE INCLUDES:
                 REM    KEYDESIRED$
                 REM    KEYNODEPOINTER
                 REM    KEYNODEKEYCOUNT
                 REM    KEYSLOT
                 REM    KEYINTERIORNODEFLAG (=false)
                 KEYDESIRED$=KEYTEMP$
                 KEYNEXTOPTIMIZEOK=TRUE
                 REM SET ARGUMENT TO NEWLY FOUND KEY AND EXIT
                 KEYNEXTKEY$=KEYDESIRED$\RETURN KEYTEMP
             FI
    NEXT KEYSLOT
    REM CAN ONLY GET HERE IF KEYDESIRED$ IS >= THAN ALL KEYS IN NODE
    REM THE FOLLOWING CODE WORKS WHETHER OR NOT WE ARE AT A LEAF NODE
    REM READ SIBLING/RIGHTMOST SON POINTER
    READ #KEYCHANNEL,KEYNODEPOINTER
    REM IF WE ARE AT LEAF, THE FOLLOWING TEST MIGHT SUCCEED
    REM IF WE ARE AT INTERIOR NODE, THE TEST WILL ALWAYS FAIL
    IF KEYNODEPOINTER=0 THEN ERROR 1001 \! NO MORE KEYS --> EOF
    GOTO KEYNEXTSEARCHSONNODE
END
!^L
SUBROUTINE KEYDELETE(KEYDELETECHANNEL,KEYDELETEKEYNUMBER,KEYDELETEKEY$)
REM THIS SUBROUTINE IS USED TO DELETE A RECORD FROM A KEY FILE.
    CALL KEYSETUP(KEYDELETECHANNEL,KEYDELETEKEYNUMBER,KEYDELETEKEY$)
    REM EMPTY TREE --> NO RECORDS TO DELETE!
    IF KEYROOT=0 THEN ERROR 1075 \ ! NO SUCH RECORD
KEYDELETEEXAMINESONNODE:
    READ #KEYCHANNEL@KEYNODEPOINTER,KEYNODEKEYCOUNT
    IF KEYNODEKEYCOUNT>=0
    THEN
        REM THIS IS AN INTERIOR NODE
        LET KEYINTERIORNODEFLAG=TRUE
    ELSE
        REM THIS IS A LEAF NODE
        LET KEYINTERIORNODEFLAG=FALSE
        LET KEYNODEKEYCOUNT=-KEYNODEKEYCOUNT
    FI
    IF KEYNODEKEYCOUNT=INT(KEYMAXKEYCOUNT/2)-KEYINTERIORNODEFLAG...
&      AND KEYNODEPOINTER<>KEYROOT
    THEN
        REM THIS SON IS EXACTLY HALF FULL (AND IT IS NOT THE ROOT NODE)
        REM WE MUST MAKE HIM MORE THAN HALF FULL...
        REM SO THAT DELETING A KEY LEAVES HIM AT LEAST HALF FULL
        REM WE CAN DO SO BY FILLING HIM FROM A SIBLING,
        REM OR MERGING HIM WITH A SIBLING
        REM HERE'S THE GAME PLAN:
        REM IF LEFT BROTHER EXISTS,
        REM THEN IF MERGABLE WITH LEFT BROTHER, THEN DO SO
        REM ELSE STEAL FROM LEFT BROTHER
        REM IF NO LEFT BROTHER, THEN THERE EXISTS A RIGHT BROTHER!
        REM (...BECAUSE KEYMAXKEYCOUNT>=4 --> AT LEAST 2 SONS IN PARENT)
        REM (FURTHER, BECAUSE "DELETE" COALESCES AS IT GOES DOWN THE B-TREE...
        REM (THE PARENT NODE IS GAURANTEED TO BE MORE THAN HALF FULL)
        REM IF MERGABLE WITH RIGHT BROTHER, THEN DO SO
        REM ELSE STEAL FROM RIGHT BROTHER
        IF KEYSLOT>0
        THEN
            REM LEFT BROTHER EXISTS! GO FIND HIM
            READ #KEYCHANNEL@KEYPOINTERPAIR(KEYPARENT,KEYSLOT-1),KEYSIBLING
            REM GET NUMBER OF KEYS OWNED BY SIBLING
            READ #KEYCHANNEL@KEYSIBLING,KEYSIBLINGKEYCOUNT
            LET KEYSIBLINGKEYCOUNT=ABS(KEYSIBLINGKEYCOUNT)
            IF KEYNODEKEYCOUNT+KEYSIBLINGKEYCOUNT...
&              <=KEYMAXKEYCOUNT-KEYINTERIORNODEFLAG
            THEN
                REM CAN MERGE NODE WITH LEFT BROTHER
                REM SWITCH NODE IDENTITIES SO WE MERGE WITH RIGHT BROTHER
                LET KEYTEMP=KEYNODEPOINTER
                LET KEYNODEPOINTER=KEYSIBLING
                LET KEYSIBLING=KEYTEMP
                LET KEYTEMP=KEYNODEKEYCOUNT
                LET KEYNODEKEYCOUNT=KEYSIBLINGKEYCOUNT
                LET KEYSIBLINGKEYCOUNT=KEYTEMP
                LET KEYSLOT=KEYSLOT-1
                GOTO KEYDELETEMERGESONS
            ELSE KEYDELETESTEALFROMLEFTBROTHER
        ELSE
            REM RIGHT BROTHER EXISTS! GO FIND HIM
            READ #KEYCHANNEL@KEYPOINTERPAIR(KEYPARENT,KEYSLOT+1),KEYSIBLING
            REM GET NUMBER OF KEYS OWNED BY SIBLING
            READ #KEYCHANNEL@KEYSIBLING,KEYSIBLINGKEYCOUNT
            LET KEYSIBLINGKEYCOUNT=ABS(KEYSIBLINGKEYCOUNT)
            IF KEYNODEKEYCOUNT+KEYSIBLINGKEYCOUNT...
&              <=KEYMAXKEYCOUNT-KEYINTERIORNODEFLAG
            THEN KEYDELETEMERGESONS
            ELSE KEYDELETESTEALFROMRIGHTBROTHER
        FI
    FI

KEYDELETESEARCHSONNODE:
    FOR KEYSLOT=0 TO KEYNODEKEYCOUNT-1
        READ #KEYCHANNEL,KEYTEMP,KEYTEMP$[1,KEYSIZE]
        IF KEYDESIRED$<=KEYTEMP$
        THEN IF KEYINTERIORNODEFLAG
             THEN
                 REM DON'T HAVE TO DELETE MATCHING KEY IN INTERIOR NODE!
                 KEYPARENT=KEYNODEPOINTER \ ! HONOR THY FATHER
                 KEYPARENTKEYCOUNT=KEYNODEKEYCOUNT
                 LET KEYNODEPOINTER=KEYTEMP
                 GOTO KEYDELETEEXAMINESONNODE
             ELSE IF KEYDESIRED$<>KEYTEMP$
                  THEN ERROR 1075 \ ! AT LEAF AND CAN'T FIND KEY
                  ELSE KEYDELETELEAFKEY
    NEXT KEYSLOT
    REM CAN ONLY GET HERE IF KEYDESIRED$ IS > THAN ALL KEYS IN NODE
    IF KEYINTERIORNODEFLAG
    THEN
        REM THIS IS AN INTERIOR NODE, THE RIGHT LINK POINTS TO SON
        KEYPARENT=KEYNODEPOINTER \ ! HONOR THY FATHER
        KEYPARENTKEYCOUNT=KEYNODEKEYCOUNT
        READ #KEYCHANNEL,KEYNODEPOINTER
        GOTO KEYDELETEEXAMINESONNODE
    ELSE ERROR 1075 \ ! LEAF NODE, AND CAN'T FIND KEY

KEYDELETELEAFKEY: REM DELETE KEY FROM LEAF
    REM ASSERT: LEAF NODE IS MORE THAN HALF FULL, OR KEYROOT=KEYNODEPOINTER
    IF KEYROOT=KEYNODEPOINTER AND KEYNODEKEYCOUNT=1
    THEN
        REM WE ARE DELETEING LAST KEY IN THE TREE, MAKE THE TREE NULL
        REM ALSO PLACE ROOT NODE ON FREE NODE LIST FOR THIS TREE
        WRITE #KEYCHANNEL@KEYNODEPOINTER,KEYFREE
        LET KEYFREE=KEYNODEPOINTER
        LET KEYROOT=0
        CALL KEYUPDATE \ ! MAKE SURE THIS CHANGE GETS TO THE FILE
        RETURN SUBROUTINE
    FI
    REM SHUFFLE KEYS TO RIGHT OF KEYSLOT, TO THE LEFT BY ONE SLOT
    FOR KEYSLOT=KEYSLOT TO KEYNODEKEYCOUNT-1
        READ #KEYCHANNEL@KEYPOINTERPAIR(KEYNODEPOINTER,KEYSLOT+1),...
&            KEYTEMP,KEYTEMP$[1,KEYSIZE]
        WRITE #KEYCHANNEL@KEYPOINTERPAIR(KEYNODEPOINTER,KEYSLOT),...
&             KEYTEMP,KEYTEMP$
    NEXT KEYSLOT
    REM SHUFFLE RIGHT SIBLING POINTER LEFT ONE SLOT
    READ #KEYCHANNEL@KEYPOINTERPAIR(KEYNODEPOINTER,KEYSLOT+1),KEYTEMP
    WRITE #KEYCHANNEL@KEYPOINTERPAIR(KEYNODEPOINTER,KEYSLOT),KEYTEMP
    REM DECREMENT # KEYS IN THIS LEAF, LEAVING NODE AT LEAST HALF FULL
    WRITE #KEYCHANNEL@KEYNODEPOINTER,-(KEYNODEKEYCOUNT-1)
    RETURN SUBROUTINE

KEYDELETEMERGESONS:
    REM MERGE KEYNODEPOINTER NODE WITH KEYSIBLING (RIGHT BROTHER)
    IF KEYINTERIORNODEFLAG
    THEN
        REM WE MUST BRING DOWN KEY FROM PARENT NODE
        READ #KEYCHANNEL@KEYPOINTERPAIR(KEYPARENT,KEYSLOT)+6,...
&            KEYMIDKEY$[1,KEYSIZE]
        REM ATTACH TO END OF THIS NODE
        WRITE #KEYCHANNEL@KEYPOINTERPAIR(KEYNODEPOINTER,KEYNODEKEYCOUNT)+6,...
&             KEYMIDKEY$
        LET KEYNODEKEYCOUNT=KEYNODEKEYCOUNT+1
    FI
    REM REMOVE KEY FROM PARENT
    IF KEYPARENTKEYCOUNT=1
    THEN
        REM PARENT IS THE ROOT NODE! THIS MAKES THE ROOT NODE GO AWAY...
        REM ADD THIS ROOT NODE TO FREE CHAIN
        WRITE #KEYCHANNEL@KEYPARENT,KEYFREE
        LET KEYFREE=KEYPARENT
        REM LET MERGED NODE BE NEW ROOT NODE
        LET KEYROOT=KEYNODEPOINTER
        REM SINCE KEYSIBLING WILL BE FREED, THE TREE HEAD WILL BE UPDATED
    ELSE
        REM THE PARENT NODE > 1/2 FULL (BECAUSE WE MADE SURE HE WAS...)
        REM SLICE OUT THE KEY FROM THE PARENT
        FOR KEYPARENTSCAN=KEYSLOT TO KEYPARENTKEYCOUNT-1
            REM READ KEY, POINTER FOR NEXT KEY
            REM THIS HAS THE DESIRED EFFECT OF:
            REM    1. LEAVING POINTER TO THIS NODE INTACT
            REM    2. COPYING RIGHTMOST SON POINTER LEFT ONE SLOT
            REM ISN'T THAT NICE?
            READ #KEYCHANNEL...
&                @KEYPOINTERPAIR(KEYPARENT,KEYPARENTSCAN+1)+6,...
&                KEYTEMP$[1,KEYSIZE],KEYTEMP
            WRITE #KEYCHANNEL...
&                 @KEYPOINTERPAIR(KEYPARENT,KEYPARENTSCAN)+6,KEYTEMP$,KEYTEMP
        NEXT KEYPARENTSCAN
        REM ADJUST PARENT NODE KEY COUNT (PARENT WAS > 1/2 FULL!)
        WRITE #KEYCHANNEL@KEYPARENT,KEYPARENTKEYCOUNT-1
    FI
    REM NOW COPY KEYS FROM RIGHT BROTHER TO THIS NODE
    FOR KEYSLOT=0 TO KEYSIBLINGKEYCOUNT-1
        READ #KEYCHANNEL...
&            @KEYPOINTERPAIR(KEYSIBLING,KEYSLOT),...
&            KEYTEMP,KEYTEMP$[1,KEYSIZE]
        WRITE #KEYCHANNEL...
&             @KEYPOINTERPAIR(KEYNODEPOINTER,KEYNODEKEYCOUNT+KEYSLOT),...
&             KEYTEMP,KEYTEMP$
    NEXT KEYSLOT
    REM SET RIGHTMOST SON OF THIS NODE TO RIGHTMOST SON OF BROTHER
    READ #KEYCHANNEL@KEYPOINTERPAIR(KEYSIBLING,KEYSLOT),KEYTEMP
    WRITE #KEYCHANNEL...
&         @KEYPOINTERPAIR(KEYNODEPOINTER,KEYNODEKEYCOUNT+KEYSLOT),KEYTEMP
    REM PLACE SIBLING NODE ON FREE NODE CHAIN
    WRITE #KEYCHANNEL@KEYSIBLING,KEYFREE
    LET KEYFREE=KEYSIBLING
    CALL KEYUPDATE \ ! MAKE SURE FREE CHAIN HEAD GETS WRITTEN BACK TO FILE
    REM NOW NODE IS > 1/2 FULL, GO ABOUT OUR BUSINESS
    REM ADJUST KEYCOUNT OF THIS SON
    REM THIS ALSO POSITIONS FILE SO WE CAN SEARCH SON NODE
    KEYNODEKEYCOUNT=KEYNODEKEYCOUNT+KEYSIBLINGKEYCOUNT
    IF KEYINTERIORNODEFLAG
    THEN WRITE #KEYCHANNEL@KEYNODEPOINTER,KEYNODEKEYCOUNT
    ELSE WRITE #KEYCHANNEL@KEYNODEPOINTER,-KEYNODEKEYCOUNT
    GOTO KEYDELETESEARCHSONNODE

KEYDELETESTEALFROMRIGHTBROTHER:
    REM RIGHT BROTHER HAS TOO MANY KEYS TO ALLOW MERGE
    REM STEAL MAX(1,HALF HIS EXCESS) KEYS
    KEYSTOSTEAL=INT((KEYSIBLINGKEYCOUNT-INT(KEYMAXKEYCOUNT/2))/2)+1
    REM COPY KEY IN PARENT THAT POINTS TO THIS SON...
    REM TO END OF THIS SON IF THIS SON IS AN INTERIOR NODE
    IF KEYINTERIORNODEFLAG
    THEN
        READ #KEYCHANNEL@KEYPOINTERPAIR(KEYPARENT,KEYSLOT)+6,...
&            KEYMIDKEY$[1,KEYSIZE]
        WRITE #KEYCHANNEL...
&             @KEYPOINTERPAIR(KEYNODEPOINTER,KEYNODEKEYCOUNT)+6,KEYMIDKEY$
    FI
    REM REPLACE KEY IN PARENT THAT POINTS TO THIS SON...
    REM BY LARGEST KEY REMOVED FROM RIGHT BROTHER
    READ #KEYCHANNEL@KEYPOINTERPAIR(KEYSIBLING,KEYSTOSTEAL-1)+6,...
&        KEYMIDKEY$[1,KEYSIZE]
    WRITE #KEYCHANNEL@KEYPOINTERPAIR(KEYPARENT,KEYSLOT)+6,KEYMIDKEY$
    REM COPY KEYS TO STEAL FROM RIGHT BROTHER TO THIS NODE
    REM DON'T COPY LAST KEY IF AN INTERIOR NODE
    FOR KEYSLOT=0 TO KEYSTOSTEAL-1-KEYINTERIORNODEFLAG
        READ #KEYCHANNEL@KEYPOINTERPAIR(KEYSIBLING,KEYSLOT),...
&            KEYTEMP,KEYTEMP$[1,KEYSIZE]
        REM ...+KEYINTERIORNODEFLAG... BELOW HANDLES KEY COPIED FROM PARENT
        WRITE #KEYCHANNEL...
&             @KEYPOINTERPAIR(KEYNODEPOINTER,...
&                             KEYNODEKEYCOUNT+KEYINTERIORNODEFLAG+KEYSLOT),...
&             KEYTEMP,KEYTEMP$
    NEXT KEYSLOT
    IF KEYINTERIORNODEFLAG
    THEN
        REM IF INTERIOR NODE COPY POINTER OF LAST KEY TO STEAL AS RIGHT SON PTR
        READ #KEYCHANNEL@KEYPOINTERPAIR(KEYSIBLING,KEYSLOT),KEYTEMP
        REM ...+1... BELOW ACCOUNTS FOR KEY COPIED FROM PARENT
        WRITE #KEYCHANNEL...
&             @KEYPOINTERPAIR(KEYNODEPOINTER,KEYNODEKEYCOUNT+1+KEYSLOT),...
&             KEYTEMP
    ELSE
        REM IF LEAF NODE, PLANT NEW RIGHT SIBLING POINTER AT END OF THIS NODE
        WRITE #KEYCHANNEL...
&              @KEYPOINTERPAIR(KEYNODEPOINTER,KEYNODEKEYCOUNT+KEYSLOT),...
&              KEYSIBLING
    FI
    REM REMOVE COPIED KEYS FROM RIGHT BROTHER
    FOR KEYSLOT=KEYSTOSTEAL TO KEYSIBLINGKEYCOUNT-1
        READ #KEYCHANNEL@KEYPOINTERPAIR(KEYSIBLING,KEYSLOT),...
&            KEYTEMP,KEYTEMP$[1,KEYSIZE]
        WRITE #KEYCHANNEL...
&             @KEYPOINTERPAIR(KEYSIBLING,KEYSLOT-KEYSTOSTEAL),...
&             KEYTEMP,KEYTEMP$
    NEXT KEYSLOT
    REM COPY RIGHTMOST SON POINTER OF SIBLING LEFT TO FINISH REMOVE
    READ #KEYCHANNEL@KEYPOINTERPAIR(KEYSIBLING,KEYSLOT),KEYTEMP
    WRITE #KEYCHANNEL...
&         @KEYPOINTERPAIR(KEYSIBLING,KEYSLOT-KEYSTOSTEAL),KEYTEMP
    REM ADJUST COUNT OF KEYS IN RIGHT SON
    LET KEYSIBLINGKEYCOUNT=KEYSIBLINGKEYCOUNT-KEYSTOSTEAL
    WRITE #KEYCHANNEL@KEYSIBLING,...
&         IF KEYINTERIORNODEFLAG
          THEN KEYSIBLINGKEYCOUNT ELSE -KEYSIBLINGKEYCOUNT FI
    REM ADJUST COUNT OF KEYS IN LEFT SON
    KEYNODEKEYCOUNT=KEYNODEKEYCOUNT+KEYSTOSTEAL
    WRITE #KEYCHANNEL@KEYNODEPOINTER,...
&         IF KEYINTERIORNODEFLAG
          THEN KEYNODEKEYCOUNT ELSE -KEYNODEKEYCOUNT FI
    REM STEAL FROM RIGHT BROTHER IS COMPLETE!
    GOTO KEYDELETESEARCHSONNODE

KEYDELETESTEALFROMLEFTBROTHER:
    REM LEFT BROTHER HAS TOO MANY KEYS TO ALLOW MERGE
    REM STEAL MAX(1,HALF HIS EXCESS) KEYS
    KEYSTOSTEAL=INT((KEYSIBLINGKEYCOUNT-INT(KEYMAXKEYCOUNT/2))/2)+1
    REM IF LEAF NODE, REPLACE KEY IN PARENT THAT POINTS TO LEFT SON...
    REM WITH LARGEST KEY NOT STOLEN FROM THAT SON.
    REM IF INTERIOR NODE, REPLACE KEY IN PARENT THAT POINTS TO LEFT SON...
    REM SMALLEST KEY REMOVED FROM LEFT BROTHER
    READ #KEYCHANNEL...
&        @KEYPOINTERPAIR(KEYSIBLING,...
&                        KEYSIBLINGKEYCOUNT-KEYSTOSTEAL...
&                                          -1+KEYINTERIORNODEFLAG)+6,...
&        KEYTEMP$[1,KEYSIZE]
    REM WE WILL NEED KEY FROM PARENT LATER IF THIS IS AN INTERIOR NODE
    READ #KEYCHANNEL...
&        @KEYPOINTERPAIR(KEYPARENT,KEYSLOT-1)+6,...
&        KEYMIDKEY$[1,KEYSIZE]
    WRITE #KEYCHANNEL@KEYPOINTERPAIR(KEYPARENT,KEYSLOT-1)+6,KEYTEMP$
    REM PARENT NODE NOW COMPLETELY FIXED
    REM MAKE ROOM IN LEFT PART OF THEIF NODE FOR KEYS TO STEAL
    REM FIRST, MOVE RIGHT SON/SIBLING POINTER RIGHT ONE SLOT
    READ #KEYCHANNEL@KEYPOINTERPAIR(KEYNODEPOINTER,KEYNODEKEYCOUNT),KEYTEMP
    WRITE #KEYCHANNEL...
&         @KEYPOINTERPAIR(KEYNODEPOINTER,KEYNODEKEYCOUNT+KEYSTOSTEAL),KEYTEMP
    FOR KEYSLOT=KEYNODEKEYCOUNT-1 TO 0 STEP -1
        READ #KEYCHANNEL...
&            @KEYPOINTERPAIR(KEYNODEPOINTER,KEYSLOT),...
&            KEYTEMP,KEYTEMP$[1,KEYSIZE]
        WRITE #KEYCHANNEL...
&             @KEYPOINTERPAIR(KEYNODEPOINTER,KEYSLOT+KEYSTOSTEAL),...
&             KEYTEMP,KEYTEMP$
    NEXT KEYSLOT
    IF KEYINTERIORNODEFLAG
    THEN
        REM USE KEY FROM PARENT AS LARGEST STOLEN KEY IF NOT A LEAF NODE
        REM ALSO, COPY RIGHTMOST SON POINTER OF LEFT SON...
        REM FOR USE AS POINTER FOR KEY TAKEN FROM PARENT
        READ #KEYCHANNEL@KEYPOINTERPAIR(KEYSIBLING,KEYSIBLINGKEYCOUNT),KEYTEMP
        WRITE #KEYCHANNEL...
&             @KEYPOINTERPAIR(KEYNODEPOINTER,KEYSTOSTEAL-1),...
&             KEYTEMP,KEYMIDKEY$
    FI
    REM COPY KEYS TO STEAL FROM LEFT BROTHER TO THIS NODE
    REM DON'T COPY LEAST KEY IF AN INTERIOR NODE
    FOR KEYSLOT=0 TO KEYSTOSTEAL-1-KEYINTERIORNODEFLAG
        READ #KEYCHANNEL...
&            @KEYPOINTERPAIR(KEYSIBLING,...
&                            KEYSIBLINGKEYCOUNT+KEYSLOT...
&                            -(KEYSTOSTEAL-KEYINTERIORNODEFLAG)),...
&            KEYTEMP,KEYTEMP$[1,KEYSIZE]
        WRITE #KEYCHANNEL@KEYPOINTERPAIR(KEYNODEPOINTER,KEYSLOT),...
&             KEYTEMP,KEYTEMP$
    NEXT KEYSLOT
    IF NOT KEYINTERIORNODEFLAG
    THEN
        REM IF LEAF NODE, PLANT RIGHT SIBLING POINTER AT END OF VICTIM NODE
        WRITE #KEYCHANNEL...
&             @KEYPOINTERPAIR(KEYSIBLING,KEYSIBLINGKEYCOUNT-KEYSTOSTEAL),...
&             KEYNODEPOINTER
    FI
    REM ADJUST COUNT OF KEYS IN LEFT SON
    LET KEYSIBLINGKEYCOUNT=KEYSIBLINGKEYCOUNT-KEYSTOSTEAL
    WRITE #KEYCHANNEL@KEYSIBLING,...
&         IF KEYINTERIORNODEFLAG
          THEN KEYSIBLINGKEYCOUNT ELSE -KEYSIBLINGKEYCOUNT FI
    REM ADJUST COUNT OF KEYS IN THIS SON
    LET KEYNODEKEYCOUNT=KEYNODEKEYCOUNT+KEYSTOSTEAL
    WRITE #KEYCHANNEL@KEYNODEPOINTER,...
&         IF KEYINTERIORNODEFLAG
          THEN KEYNODEKEYCOUNT ELSE -KEYNODEKEYCOUNT FI
    REM STEAL FROM LEFT BROTHER IS COMPLETE!
    GOTO KEYDELETESEARCHSONNODE
END
!
! 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)
