%INTEGERFN ADDQ(%INTEGER ADD,N,POSITION)
!
!  A FREE POSITION SET POSITION = 1, CHECK 0 FIRST
!
%LONGINTEGER II,JJ,KK
%INTEGER I,J,K
%IF POSITION > N %THEN %RESULT = -1
     K = (POSITION -1) >>6
     J = ADD + 8 * K
    II = LONGINTEGER(J)
     I = POSITION - (K<<6)
    JJ = X'8000000000000000'>>(I-1)
    KK = II & JJ
%IF KK # 0 %THEN %RESULT = -1     !CHECK IF USED
    II = II ! JJ                  !RETURN IF FREE
     LONGINTEGER(J) = II
%RESULT = 0
%END
!
!
%INTEGERFN SETQ (%INTEGER ADD,N,POSITION)
!
!   ADD = ADDRESS OF BIT MAP, N = NO. OF RECORDS, POSITION = BIT TO BE SET
!
%LONGINTEGER II,JJ,KK
%INTEGER I,J,K
%IF POSITION > N %THEN %RESULT = -1
     K = (POSITION -1) >>6
     J = ADD + 8 * K
    II = LONGINTEGER (J)                 !FETCH 64 BIT WORD
     I = POSITION - (K<<6)               !CALC. POSITION WITHIN WORD
    JJ = X'8000000000000000' >> (I-1)
    KK = II & JJ                         !CHECK IF FREE
%IF KK # 0 %THEN %RESULT = -1            !ALREADY IN USE
    II = -- & (KK ~ X'FFFFFFFFFFFFFFFF') !SET BIT
    LONGINTEGER (J) = II                 !STORE IT BACK
%RESULT = 0
%END
!
!
%INTEGERFN GETQ(%INTEGER ADD,N)
!
!   ADD = ADDRESS OF START OF BIT MAP
!     N = NO. OF RECORDS IN FILE
!   TESTING DONE ON 64 BIT WORDS
!   BIT MAPS SET TO ALL 1'S INITIALLY.  -1 = FREE, 0 = USED.
!   THIS SEARCHES FOR FIRST FREE POSITION AND RETURNS IT IN RESULT.
!   REMIT = -1 IMPLIES NO FREE SPACE.
!
!
%LONGINTEGER II
%INTEGER I, COUNT, 
     POSITION = -1
%CYCLE I = 0,1,(N-1)//64
     II = LONGINTEGER (ADD + 8 * I)
     *LSD_II
     *SHZ_COUNT
     *ST_II
%IF COUNT = 0 %AND II # 0 %THEN POSITION = 64 * I + COUNT + 1 %AND %EXIT
%REPEAT
%IF POSITION > N %THEN POSITION = -1
%RESULT = POSITION
%END
!
!
%ROUTINE SPLITRR (%INTEGER P)
%INTEGER AUXP
     AUXP = FINDEX(P)_RP ; FINDEX(AUXP)_RBIT = FALSE
     FINDEX(P)_RP = FINDEX(AUXP_LP ; FINDEX(P)_RBIT = FALSE
     FINDEX(AUXP)_LP = P ; P = AUXP
%END
%ROUTINE SPLITRL (P)
%INTEGER AUXP
     AUXP = FINDEX(FINDEX(P)_RP)_LP
     FINDEX(FINDEX(P)_RP)_LBIT = FALSE
     FINDEX(FINDEX(P)_RP)LP = FINDEX(AUXP)_RP
     FINDEX(AUXP)_RP = FINDEX(P)_RP
     FINDEX(P)_RP = FINDEX(AUXP)_LP
     FINDEX(P)_RBIT = FALSE
     FINDEX(AXP)_LP = P
     P = AUXP
%END
!
!
%ROUTINE SPLITLL (P)
%INTEGER AUXP
     AUXP = FINDEX(P)_LP
     FINDEX(AUXP)_LBIT = FALSE
     FINDEX(P)_LP = FINDEX(AUXP)_RP
     FINDEX(P)_LBIT = FALSE
     FINDEX(AUXP)_LP = P
     P = AUXP
%END
!
!
%ROUTINE SPLITLR (P)
%INTEGER AUXP
     AUXP = FINDEX(FINDEX(P)_LP)_RP
     FINDEX(FINDEX(P)_LP)_RP = FINDEX(AUXP)_LP
     FINDEX(FINDEX(P)_LP)_RBIT = FALSE
     FINDEX(AUXP)_LP = FINDEX(P)_LP
     FINDEX(P)_LP = FINDEX(AUXP)_RP
     FINDEX(P)_LBIT = FALSE
     FINDEX(AUXP)_RP = P
     P = AUXP
%END
!
!
%INTEGERFN SYMINS (%STRING NEWKEY, %INTEGER ROOT, %BYTEINTEGER ROOTBIT)
!
!   INSERTS NEW ENTRY IN INDEX
!
!   BAYER - ACTA INFORMATICA I, 290-306 (1972)
!
!   THE POSITION IS RETURNED AS THE RESULT OF SUCCESSFUL INSERTION
!   0 IS RETURNED IF THE KEY IS ALREADY PRESENT
!   -1 IS RETURNED IF THE INDEX IS FULL
!
%ROUTINE SYMSERT(%INTEGER P, %BYTEINTEGER BIT)
%INTEGER I, EVENT
%INTEGER TRUE = 1, FALSE = 0
%IF P = 0 %THEN %START
!
!   INSERT X AS NEW LEAF
!
     L = GETQ (TCB_INDEXADDR,TCB_NRECS)
%IF I < 0 %THEN %SIGNAL %EVENT 14
     P = I ; FINDEX(P)_KEY = NEWKEY
     POSITION = P ; BIT = TRUE ;
     FINDEX(P)_LP = FALSE ; FINDEX(P)_RP = FALSE ; FINDEX(P)_LBIT = FALSE
     FINDEX(P)_RBIT = FALSE
%FINISH

%ELSE %IF NEWKEY = KEY(P) %THEN %SIGNAL %EVENT 13
%ELSE %IF NEWKEY < KEY(P) %THEN %START
!
!   INSERT NEWKEY IN LEFT SUBTREE
!
     SYMSERT(FINDEX(P)_LP,FINDEX(P)_LBIT)
%IF FINDEX(P)_LBIT = TRUE %THEN %START
     SPLITLL(P) ; BIT = TRUE
     %FINISH
%ELSE %IF FINDEX(P)_RBIT = TRUE %THEN %START
     SPLITLR(P) ; BIT = TRUE
     %FINISH
%ELSE %SIGNAL %EVENT 12
%FINISH

%ELSE %START
!
!   INSERT KEY IN RIGHT SUBTREE
!
     SYMSERT (FINDEX(P)_RP,FINDEX(P)_RBIT)
     %IF FINDEX(P)_RBIT = TRUE %THEN %START
          %IF FINDEX(FINDEX(P)_RP)_RBIT = TRUE %THEN %START
               SPLITRR(P)
               BIT = TRUE
          %FINISH
          %ELSE %IF FINDEX(FINDEX(P)_RP)_LBIT = TRUE %THEN %START
               SPLITRL(P)
               BIT = TRUE
          %FINISH
     %FINISH
     %ELSE %SIGNAL %EVENT 12
%END
!
!
%ON %EVENT 12, 13, 14 %START
     EVENT = EVENTING >> 8 & 15
%IF EVENT = 12 %THEN %RESULT =
%IF EVENT = 13 %THEN %RESULT = 0
%IF EVENT = 14 %THEN %RESULT = -1
%FINISH

SYMSERT(ROOT,ROOTBIT)

%END
!
!
%INTEGERFN SYMDEL(%STRING KEY, %INTEGER ROOT)
!
!   RECURSIVE B-TREE DELETION
!
%PROCEDURE SYMDELETE (%INTEGER P)
     %INTEGER X, D
!
!   DID WE FIND THE KEY TO BE DELETED
!
     %IF KEY = FINDEX(P)_KEY %THEN X = P
     %IF KEY \< FINDEX(P)_KEY %OR FINDEX(P)_LP # 0 %THEN %START
         SYMDELETE (FINDEX(P)_LP)
!
!   CASES D, E, G
!
     %IF FINDEX(P)_LBIT = TRUE %THEN %START
!
!   CASE G
!
          FINDEX(P)_LBIT = FALSE
          %SIGNAL %EVENT 12
     %FINISH
!
!CASES E & D
!
     %ELSE %START
          %IF FINDEX(P)_RBIT = TRUE %THEN %START
!
!   CASE E
!
     D = FINDEX(P)_RP, FINDEX(P)_RP = FINDEX(D)_LP
     FINDEX(D)_LP = P ; P = D
          %IF FINDEX(FINDEX(FINDEX(P)_LP)_RP)_LBIT = TRUE
          %THEN %START
            SPLITRL(FINDEX(P)_LP) ; FINDEX(P)_LBIT = TRUE
          %FINISH
%ELSE %IF FINDEX(FINDEX(FINDEX(P)_LP)_RP)_RBIT = TRUE %THEN %START
     SPLITRR (FINDEX(P)_LP) ; FINDEX(P)_LBIT = TRUE
     %FINISH
     %SIGNAL %EVENT 12
%FINISH ;   !END OF CASE E

%ELSE %START
!
!   CASE D
!
     FINDEX(P)_RBIT = TRUE
          %IF FINDEX(FINDEX(P)_RP)_LBIT = TRUE %THEN %START
          SPLITRL(P) ; %SIGNAL %EVENT 12
          %FINISH
          %ELSE %IF FINDEX(FINDEX(P)_RP)_RBIT = TRUE %THEN %START
          SPLITRR(P) ; %SIGNAL %EVENT 12
          %FINISH ;   !END OF CASE D
     %FINISH ;   !END OF D AND E
%FINISH ;   !END OF SL AND CASES D, E, G

%ELSE %IF KEY >/ FINDEX(P)_KEY %OR FINDEX(P)_RP # 0 %THEN %START
!
!   GL
!
     SYMDELETE (FINDEX(P)_RP)
!
!   CASES B, C & F
!
%IF FINDEX(P)_RBIT = TRUE %THEN %START
!
!   CASE F
!
     FINDEX(P)_RBIT = FALSE ; %SIGNAL %EVENT 12
%FINISH
!
!   CASES B & C
!
%ELSE %START
     %IF FINDEX(P)LBIT = TRUE %THEN %START
!
!   CASE C
!
     D = FINDEX(P)_LP ; FINDEX(P)_LP = FINDEX(D)_RP
     FINDEX(D)_RP = P ; P = D
          %IF FINDEX(FINDEX(FINDEX(P)_RP)_LP)_RBIT = TRUE %THEN %START
            SPLITLR(FINDEX(P)_RP)
            FINDEX(P)_RBIT = TRUE
          %FINISH

          %ELSE %IF FINDEX(FINDEX(FINDEX(P)_RP)_LP)_LBIT = TRUE %THEN %START

            SPLITLL(FINDEX(P)_RP)
            FINDEX(P)_RBIT = TRUE
          %FINISH
          %SIGNAL %EVENT 12
%FINISH    !END OF CASE C
!
!   CASE B
!
%ELSE %START
     FINDEX(P)_LBIT = TRUE
          %IF FINDEX(FINDEX(P)_LP)_RBIT = TRUE %THEN %START
            SPLITLR(P) ; %SIGNAL %EVENT 12
          %FINISH
          %ELSE %IF FINDEX(FINDEX(P)_LP)_LBIT = TRUE %THEN %START
            SPLITLL(P) ; %SIGNAL %EVENT 12
          %FINISH
     %FINISH    !CASE B
   %FINISH    !CASES B & C
%FINISH     !GL AND CASES B, C & F
!
!   ARRIVED AT NEXT LEAF OR NEXT TO ONE - CASE A
!
%ELSE %START
     %IF X = 0 %THEN %SIGNAL %EVENT 13
     FINDEX(X)_KEY = FINDEX(P)_KEY
          %IF FINDEX(P)_LBIT = TRUE %THEN D = FINDEX(P)_LP
               %ELSE D = FINDEX(P)_RP
          ADDQ(TCB_INDEXADDR,TCB_NRECS,P) ; P = D
          %IF P # 0 %THEN %SIGNAL %EVENT 12
     %FINISH
%FINISH    ! OF SYMDELETE
     %ON %EVENT 12, 13 %START
          EVENT = EVENTING >> 8 & 15
     %IF EVENT = 12 %THEN %RESULT = 0
     %IF EVENT = 13 %THEN %RESULT = -1
%FINISH
     X = 0
     %IF ROOT = 0 %THEN %RESULT = -1
     SYMDELETE(ROOT)
%END ;     ! OF SYMDEL