Trailing-Edge
-
PDP-10 Archives
-
704rmsf2
-
10,7/rms10/rmssrc/rmsidx.b36
There are 6 other files named rmsidx.b36 in the archive. Click here to see a list.
MODULE INDEX =
BEGIN
GLOBAL BIND IDXV = 1^24 + 0^18 + 14; !EDIT DATE: 19-MAY-77
%([
FUNCTION: THIS MODULE CONTAINS ALL ROUTINES WHICH TRAVERSE AND
MODIFY THE INDEX STRUCTURE OF AN RMS-20 INDEXED FILE.
AUTHOR: S. BLOUNT
THIS SOFTWARE IS FURNISHED UNDER A LICENSE AND MAY ONLY BE USED
OR COPIED IN ACCORDANCE WITH THE TERMS OF SUCH LICENSE.
!COPYRIGHT (C) 1977, 1979 BY DIGITAL EQUIPMENT CORPORATION
********** TABLE OF CONTENTS **************
ROUTINE FUNCTION
======= ========
MAKEIRECORD CREATE AN INDEX RECORD
GETROOT LOCATE, LOCK, AND MAP THE ROOT BUCKET
SINDEXBKT SEARCH AN INDEX BUCKET FOR A KEY STRING
FOLLOWPATH FOLLOW THE INDEX DOWN TO DATA LEVEL
FNDREC TRAVERSE INDEX TO ANY LEVEL
IDXUPDATE UPDATE THE INDEX STRUCTURE
GTBKTPTR GET THE NEXT BUCKET DOWNWARD IN THE TREE
GTNBKT GET NEXT BUCKET IN THIS LEVEL
SPTINDEX SPLIT AN INDEX BUCKET
INSRTIRECORD INSERT AN INDEX RECORD
FNDDATA TRAVERSE INDEX FROM ROOT TO DATA
REVISION HISTORY:
EDIT DATE WHO PURPOSE
==== ==== === =======
1 27-OCT-76 SB RELEASE BKT IF GTBKTPTR FAILS
2 21-DEC-76 SB CHANGES FOR LOCKING
3 1-FEB-77 SB MAKE INSRTIREC RELEASE INDEX
BUCKET IF THERE WAS NO HIGH-KEY
4 1-FEB-77 SB FIX BUG IN SPTINDEX RE LOC OF SPLIT
5 17-FEB-77 SB DONT INSERT NEW IDX REC IF OLD KEY
IS SAME AS NEW HI-KEY
6 18-FEB-77 SB ADD CALL TO ADJIPTR IF THE KEY OF
THE HI-KEY RECORD .NEQ. INDEX KEY
7 18-FEB-77 SB FIX BUG IN GTBKTPTR ON GETTING WRONG
BUCKET SIZE WHEN GOING TO DATA
8 21-FEB-77 SB FIX BUG IN INSRTIREC IF 3-BKT SPLIT
WITH "NOHIKEY" SET
9 23-FEB-77 SB CHECK FOR FLGHIKEY IN SINDEXBKT (SIXBIT KEYS)
10 23-FEB-77 SB MOVE HIKEY FLAG TO NEW REC ON INSRTIREC
11 2-MAR-77 SB FIX SINDEXBKT TO HANDLE <0 KEYS
12 29-MAR-77 SB FIX DEBUG ERROR IN GTBKTPTR
13 19-MAY-77 SB ADD BIG COMMENT TO IDXUPD
*************************************************
* *
* NEW REVISION HISTORY *
* *
*************************************************
****************** Start RMS-10 V1.1 *********************
********************* TOPS-10 ONLY ***********************
PRODUCT MODULE SPR
EDIT EDIT QAR DESCRIPTION
====== ====== ===== ===========
100 14 Dev Make declarations for routine names
be EXTERNAL ROUTINE so RMS will compile
under BLISS V4 (RMT, 10/22/85).
***** END OF REVISION HISTORY *****
])%
%([ FORWARD DECLARATIONS ])%
FORWARD ROUTINE FNDREC,
GTNBKT,
INSRTIRECORD,
GTBKTPTR,
SPTINDEX;
%([ EXTERNAL DECLARATIONS ])%
EXTERNAL ROUTINE
CRASH, ! DEBUGGING
ALCBKT, ! ALLOCATE A NEW BKT
ALCRFA, ! ALLOCATE A NEW RFA
GETBKT, ! GET A BUCKET
CKEYKK, ! COMPARE NON-SEGMENTED KEY STRINGS
DUMPRD, ! DUMP A RECORD DESCRIPTOR
DUMPHEADER, ! DUMP A BUCKET HEADER
CKEYKU, ! COMPARE KEY TO USER KEY
GETIDB, ! GET THE INDEX DESCRIPTOR
PUTBKT, ! PUT IT BACK AGAIN
MAKROOT, ! MAKE A NEW ROOT
MOVEKEY, ! MOVE A KEY STRING
SDATABKT, ! SEARCH A DATA BUCKET
LOOP1,
DUMP; ! SAME
%([ ERROR MESSAGES REFERENCED IN THIS MODULE ])%
EXTERNAL
MSGLOOP, ! LOOP STRUCTURE IS BAD
MSGCOUNT, ! BAD COUNTER VALUE
MSGFLAGS, ! BAD FLAGS
MSGPTR, ! BAD POINTER VALUE
MSGSPLIT, ! BAD SPLIT PARAMETERS
MSGFAILURE, ! ROUTINE FAILED
MSGNOSPACE, ! NO SPACE IN INDEX BUCKET
MSGLEVEL, ! BAD LEVEL NUMBER FOUND
MSGRCHANGED, ! ROOT CHANGED
MSGCANTGETHERE, ! BAD CODE FLOW
MSGINPUT; ! BAD INPUT
REQUIRE 'RMSREQ';
EXTDECLARATIONS;
! MAKEIRECORD
! ===========
! ROUTINE TO CREATE AN INDEX RECORD IN AN INDEXED FILE.
! INPUT:
! BUCKETNUMBER BUCKET TO PUT IN THE INDEX RECORD
! RECORDPTR ADDRESS TO WRITE RECORD
! KEYPTR ADDRESS OF KEY STRING TO GO IN THE INDEX RECORD
! OUTPUT:
! <NO VALUE RETURNED>
! INPUT ARGUMENTS MODIFIED:
! <NONE>
! ROUTINES CALLED:
! <NONE>
! CALLED BY:
! INSRTIRECORD
GLOBAL ROUTINE MAKEIRECORD ( BUCKETNUMBER, RECORDPTR, KEYPTR ): NOVALUE =
BEGIN
ARGUMENT (BUCKETNUMBER,VALUE); ! # OF BUCKET
ARGUMENT (RECORDPTR,BASEADD); ! ARG PACKET
ARGUMENT (KEYPTR,BASEADD); ! ADDRESS OF DATA RECORD
MAP
RECORDPTR: POINTER,
KEYPTR: POINTER;
TRACE ( 'MAKEIRECORD');
CHECKINPUT (BUCKETNUMBER,GTR,ZERO);
%([ STORE FLAGS AND BUCKET NUMBER ])%
RECORDPTR [ IRFLAGS ] = DEFIRFLAGS; ! USE THE DEFAULT
RECORDPTR [ IRBUCKET ] = .BUCKETNUMBER;
%([ NOW, MOVE THE STRING ])%
INC ( RECORDPTR, IRHDRSIZE );
MOVEWORDS ( %(FROM)% .KEYPTR,
%(TO)% .RECORDPTR,
%(SIZE)% .KDB [ KDBKSZW ] );
RETURN
END; %(OF MAKEIRECORD)%
! GETROOT
! =======
! ROUTINE TO GET THE ROOT OF AN INDEX STRUCTURE
! THIS ROUTINE IS RESPONSIBLE FOR LOCATING AND MAPPING
! THE CURRENT ROOT OF THE INDEX. IF THERE IS NOT A CURRENT
! ROOT, THEN THE FILE PROLOGUE MUST
! BE READ TO FIND THE NEW ROOT.
!
! INPUT:
! RECDESC = RECORD DESCRIPTOR
! <NO FIELDS USED AS INPUT>
! BKTDESC = BUCKET DESCRIPTOR OF ROOT (RETURNED)
! OUTPUT:
! TRUE: OK
! FALSE: ERROR ( ERROR CODE IS IN USRSTS )
! BUSY
! NO FREE CORE AVAILABLE
!
! NOTES:
! ROUTINES CALLED:
! GETIDB
! LOCKIT
GLOBAL ROUTINE GETROOT ( RECDESC, BKTDESC ) =
BEGIN
ARGUMENT (RECDESC,BASEADD); ! RECORD DESCTIPROR
ARGUMENT (BKTDESC,BASEADD);
MAP
BKTDESC: POINTER,
RECDESC: POINTER;
LOCAL
IDBPTR: POINTER, ! PTR TO INDEX DESCRIPTOR
PLOGBKTDESC: FORMATS[ BDSIZE ], ! BUCKET DESC FOR FILE PROLOGUE
LOCKFUNCTION, ! FUNCTION CODE FOR ENQ/DEQ
LOOPCOUNT, ! KEEP TRACK OF OUT PROGRESS
BUCKETSIZE, ! SIZE OF ROOT BUCKET
ROOTBUCKET; ! ROOT BUCKET NUMBER
REGISTER
ROOTPOINTER: POINTER; ! PTR TO ROOT BUCKET
LITERAL MAXLOOPS = 1; ! MAX # OF TIMES WE WILL LOOP
TRACE ( 'GETROOT' );
LOOPCOUNT = ZERO; ! CLEAR OUR LOOP COUNTER
BUCKETSIZE = .KDB [ KDBIBKZ ]; ! GET BUCKET SIZE
%([ HERE IS THE BIG LOOP. THIS LOOP IS EXECUTED MORE
THAN ONCE ONLY IF THERE IS A ROOT IN THE KDB ])%
REPEAT %(FOREVER)%
BEGIN
IF .LOOPCOUNT GTR MAXLOOPS THEN RMSBUG ( MSGLOOP );
%([ GET THE CURRENT BUCKET NUMBER ])%
ROOTBUCKET = .KDB [ KDBROOT ];
IF .ROOTBUCKET ISNT ZERO
THEN %(THERE MUST BE AN INDEX FOR THIS KEY)%
BEGIN
IF CALLGETBKT ( %(BKT)% LCI ( ROOTBUCKET ),
%(SIZE)% LCI ( BUCKETSIZE ),
%(LOCK)% PCI ( FALSE ),
%(DESC)% BPT ( BKTDESC ) ) IS FALSE
THEN
RETURN FALSE;
ROOTPOINTER = .BKTDESC [ BKDBKTADR ]; ! GET ADDRESS
IF CHKFLAG ( ROOTPOINTER [ BHFLAGS ], BHFLGROOT )
ISON THEN GOODRETURN; ! THIS IS THE ROOT
%([ THIS BUCKET IS NO LONGER THE ROOT ])%
RMSBUG ( MSGRCHANGED )
END; %(OF IF ROOTBUCKET ISNT ZERO)%
%([ WE MUST READ THE INDEX DESCRIPTOR IN THE FILE
PROLOGUE ])%
IF (IDBPTR = CALLGETIDB ( LCT ( PLOGBKTDESC ) )) IS FALSE
THEN
RETURN FALSE;
%([ GET THE NEW ROOT BUCKET NUMBER ])%
KDB [ KDBROOT ] = .IDBPTR [ IDBROOT ];
%([ RETURN THE PROLOGUE BUCKET ])%
CALLPUTBKT ( %(NO UPDATE)% PCI ( FALSE ),
%(BUCKET)% LCT ( PLOGBKTDESC ) );
%([ NOW, CHECK IF THERE IS A ROOT YET FOR THIS INDEX.
THERE WILL BE A VALID ROOT EXCEPT WHERE A FILE WAS
"$CREATED" WITHOUT ANY RECORDS, AND THEN THE FILE
WAS OPENED FOR INPUT. ])%
IF .KDB [ KDBROOT ] IS ZERO
THEN %(THERE IS NO ROOT)%
BEGIN
IF SEQADR
THEN %(WE SHOULD RETURN EOF)%
USRSTS = ER$EOF
ELSE %(WE SHOULD RETURN RNF)%
USRSTS = ER$RNF;
BADRETURN
END %(OF IF THERE IS NO ROOT)%
ELSE
CLRFLAG ( KDB [ KDBFLAGS ], FLGNOINDEX );
%([ BUMP OUR LOOP COUNTER AND GO BACK AND TRY AGAIN ])%
LOOPCOUNT = .LOOPCOUNT + 1
END; %(OF REPEAT LOOP)%
RMSBUG ( MSGCANTGETHERE ) ! CAN NEVER EXECUTE THIS
END; %(OF GETROOT)%
! SINDEXBKT
! =========
! ROUTINE TO SEARCH A MAPPED, LOCKED INDEX BUCKET FOR A KEY STRING
! THIS ROUTINE SEACHES AN INDEX BUCKET FOR THE INDEX RECORD
! WHICH IS GTR OR EQUAL TO A SPECIFIED USER SEARCH KEY.
! BOTH KEY STRINGS MUST BE NON-SEGMENTED.
! INPUT:
! RECDESC RECORD DESCRIPTOR
! USERPTR ADDRESS OF SEARCH KEY STRING (K(S))
! USERSIZE SIZE OF SEARCH KEY STRING
! RECPTR ADDRESS TO BEGIN SEARCH
! .EQL. ZERO ==> START AT TOP OF BKT
! .GTR. ZERO ==> ADDRESS TO START AT
! .LSS. ZERO ==> SEARCH ONLY 1ST RECORD
! BKTDESC BUCKET DESCRIPTOR OF INDEX BUCKET
!
! OUTPUT STATUS:
! TRUE: SEARCH TERMINATED NORMALLY (SEARCH KEY IS LEQ INDEX RECORD)
! FLGLSS MAY BE SET IF K(S) < RECORD KEY
! FALSE: KEY STRING NOT FOUND
! INPUT ARGUMENTS MODIFIED
! RECORD DESCRIPTOR
! RECPTR ADDRESS OF INDEX RECORD WHICH TERMINATED SEARCH
! LASTRECPTR ADDRESS OF PREVIOUS RECORD
! ROUTINES CALLED:
! CKEYKK
GLOBAL ROUTINE SINDEXBKT ( RECDESC, BKTDESC ) =
BEGIN
ARGUMENT (RECDESC,BASEADD); ! RECORD DESCRIPTOR
ARGUMENT (BKTDESC,BASEADD); ! BUCKET DESC
MAP
RECDESC: POINTER,
BKTDESC: POINTER;
REGISTER
TEMPAC,
TEMPAC1,
TEMPAC2;
LOCAL
ENDPTR: POINTER, ! END OF BKT PTR
RECORDTOCHECK: POINTER, ! PTR USED TO SCAN BUCKET
INTERVAL, ! HALF THE # OF RECORDS LEFT TO SEARCH
BKTPTR: POINTER, ! PTR TO TOP OF BUCKET
FIRSTRECORD, ! ADDRESS OF FIRST RECORD
WORDS, ! WORDS TO COMPARE FOR KEY
SLACKBYTES, ! LEFT-OVER BYTES
BYTESPERWORD, ! # OF BYTES IN EACH WORD
KEYBSZ, ! BYTE SIZE OF KEY
SIZEOFRECORD, ! TOTAL SIZE OF EACH RECORD
ADDR1, ! ADDRESS OF GIVEN KEY
ADDR2, ! ADDR OF KEY TO COMPARE AGAINST
COMPARESULT, ! RESULT OF LAST COMPARE
LASTLESSOREQUAL, ! INDICATES OUTCOME OF LAST < OR = COMPARE
COUNT, ! KEEPS TRACK OF KEY COMPARE
TEMP1, ! TEMPORARIES USED FOR STRING COMPARE
TEMP2,
TEMP5;
TRACE ('SINDEXBKT');
%([ CLEAR THE LSS FLAG IN THE RECORD DESCRIPTOR ])%
CLRFLAG ( RECDESC [ RDSTATUS ], RDFLGLSS );
%([ SET UP THE END-OF-BUCKET PTR ])%
BKTPTR = .BKTDESC [ BKDBKTADR ];
ENDPTR = .BKTPTR + .BKTPTR [ BHNEXTBYTE ];
%([ CHECK A FEW THINGS ])%
IF ( .BKTPTR [ BHTHISAREA ] ISNT .KDB [ KDBIAN ] )
OR
( .BKTPTR [ BHBTYPE ] ISNT BTYPEINDEX ) ! CHECK BKT HEADER
THEN
BEGIN
FILEPROBLEM ( FE$BHE ); ! BAD BUCKET HEADER
USEREXIT
END; %(OF IF THIS BUCKET HEADER IS BAD)%
%([ MAKE SURE BUCKET ISN'T EMPTY ])%
IF .BKTPTR [ BHNEXTBYTE ] EQL BHHDRSIZE
THEN %(NO RECORDS IN THIS BUCKET)%
BEGIN
FILEPROBLEM ( FE$BEM ); ! EMPTY BUCKET FOUND
USEREXIT
END; %(OF THERE IS NO DATA IN THIS BUCKET)%
%([ COMPUTE TOTAL SIZE OF AN INDEX RECORD ])%
SIZEOFRECORD = .KDB [ KDBKSZW ] + IRHDRSIZE;
%([ GET BYTE SIZE FOR LATER ])%
KEYBSZ = .KDB [ KDBKBSZ ];
%([ ADJUST START AND END OF SEARCH SPACE ])%
IF ( FIRSTRECORD = .RECDESC [ RDRECPTR ] ) LEQ ZERO
THEN %(START FROM FIRST RECORD IN BUCKET)%
BEGIN
IF .FIRSTRECORD LSS ZERO
THEN %(PRETEND END OF BUCKET IS AFTER FIRST RECORD)%
ENDPTR = .BKTPTR + BHHDRSIZE + .SIZEOFRECORD;
FIRSTRECORD = .BKTPTR + BHHDRSIZE
END %(OF IF RECPTR LEQ ZERO)%
ELSE %(MAKE SURE START ADDRESS IS IN BUCKET)%
BEGIN %(CHECK START ADDRESS)%
IF .FIRSTRECORD GEQ .ENDPTR
THEN RMSBUG ( MSGINPUT );
END;
%([ SET UP FIRST INTERVAL AND INITIAL RECORD TO CHECK ])%
INTERVAL = ( .ENDPTR - .FIRSTRECORD ) / ( 2 * .SIZEOFRECORD );
RECORDTOCHECK = .INTERVAL * .SIZEOFRECORD + .FIRSTRECORD;
%([ SET UP FOR KEY COMPARE ])%
BYTESPERWORD = 36 / .KEYBSZ;
WORDS = .RECDESC [ RDUSERSIZE ] / .BYTESPERWORD;
SLACKBYTES = ( .RECDESC [ RDUSERSIZE ] MOD .BYTESPERWORD );
%([ GET ADDRESS OF KEY WE'RE LOOKING FOR ])%
ADDR1 = .RECDESC [ RDUSERPTR ];
%([ MAIN LOOP ])%
REPEAT
BEGIN
%([ COMPARE STRINGS ])%
%([ THIS IS THE KEY WE'RE CHECKING AGAINST THIS TIME ])%
ADDR2 = .RECORDTOCHECK + IRHDRSIZE;
LOOKAT (' RECORD PROBE AT: ', RECORDTOCHECK );
%([ COMPARE THE ENTIRE INDEX KEY. WE WILL DO THIS
BY COMPARING EACH WORD AS A UNIT (IGNORING EXTRA
BITS IN THE WORD), AND THEN COMPARE THE SLACK BYTES. ])%
TEMPAC = FALSE; ! ASSUME NO FULL WORDS
IF .WORDS GTR ZERO
THEN %(WE MUST COMPARE THE WHOLE WORDS)%
BEGIN
COMPARESULT = 1; ! ASSUME OUR KEY IS GTR
TEMP2 = POINT ( .RECDESC [ RDUSERPTR ], 36, .BYTESPERWORD*.KEYBSZ );
TEMP5 = .TEMP2;
TEMP5< RH > = .ADDR2; ! FORM DEST ADDR
%([ COMPARE THE WHOLE WORDS IN THE KEY ])%
IF CSTRINGLE (%(SEARCH KEY)% TEMP2,
%(DEST KEY)% TEMP5,
%(SIZE)% WORDS,
%(SIZE)% WORDS ) IS FALSE
%([ IF THIS FAILED, THEN OUR SEARCH KEY IS GTR
THAN THE INDEX RECORD KEY. ])%
THEN
TEMPAC = TRUE ! EXIT FROM LOOP
ELSE
BEGIN
%([ OUR KEY IS .LEQ. THE INDEX KEY ])%
LDB ( TEMPAC1, TEMP2 ); ! GET THE BYTES
LDB ( TEMPAC2, TEMP5 );
COMPARESULT = -1; ! ASSUME LSS
TEMPAC = (IF .TEMPAC1 ! SEARCH KEY
LSS
.TEMPAC2 ! INDEX KEY
THEN
TRUE
ELSE
FALSE )
END; %(OF ELSE OUR KEY .LEQ. INDEX KEY)%
END; %(OF IF .WORDS GTR ZERO)%
%([ NOW, COMPARE THE SLACK BYTES IF THERE ARE ANY,
AND IF THE WORD COMPARISON WAS EQUAL UP TO THIS POINT ])%
IF .TEMPAC IS FALSE
THEN %(WE MUST COMPARE THE SLACK BYTES)%
BEGIN
TEMP1 = POINT ( .RECDESC [ RDUSERPTR ] + .WORDS, 36, .SLACKBYTES * .KEYBSZ );
TEMP2 = ( .ADDR2 + .WORDS );
TEMP2< LH > = .TEMP1< LH >;
%([ LOAD THE LAST SERIES OF BYTES AS A SINGLE BYTE ])%
TEMPAC1 = SCANI ( TEMP1 );
TEMPAC2 = SCANI ( TEMP2 );
IF .TEMPAC1 LSS .TEMPAC2
THEN
COMPARESULT = -1
ELSE
BEGIN
%([ OUR SLACK BYTES WERE .GEQ. INDEX BYTES ])%
COMPARESULT = ( IF .TEMPAC1 IS .TEMPAC2
THEN
0 ! EQUAL
ELSE
1 ) ! OUR KEY IS .GTR.
END %(OF ELSE KEY IS .GEQ.)%
END; %(OF COMPARE THE SLACK BYTES)%
%([ WAS OUR KEY GREATER THAN THIS ONE? ])%
IF .COMPARESULT GTR ZERO
THEN %(TRY SECOND HALF OF SEARCH SPACE)%
BEGIN %(OUR KEY IS GREATER)%
RTRACE (%STRING(' RECORD PROBE IS TOO LOW...',%CHAR(13),%CHAR(10)));
IF .RECORDTOCHECK GEQ ( .ENDPTR - .SIZEOFRECORD)
THEN %(KEY ISN'T IN BUCKET)%
BEGIN %(BADRETURN)%
RECDESC [ RDLASTRECPTR ] = .RECORDTOCHECK;
RECDESC [ RDRECPTR ] = .ENDPTR;
BADRETURN
END %(BADRETURN)%
ELSE BEGIN %(UPDATE)%
IF .INTERVAL EQL ZERO
THEN %(NEXT ONE MUST BE RIGHT)%
BEGIN
RECDESC [ RDLASTRECPTR ] = .RECORDTOCHECK;
RECDESC [ RDRECPTR ] = .RECORDTOCHECK + .SIZEOFRECORD;
IF .LASTLESSOREQUAL LSS ZERO
THEN SETLSSFLAG ( RECDESC );
GOODRETURN
END
ELSE %(WE AREN'T FINISHED YET)%
BEGIN %(ADJUST RECORD AND INTERVAL)%
RECORDTOCHECK = .RECORDTOCHECK + ( ( .INTERVAL + 1 ) / 2 ) * .SIZEOFRECORD;
INTERVAL = .INTERVAL / 2
END %(ADJUST RECORD AND INTERVAL)%
END %(UPDATE)%
END %(OUR KEY WAS GREATER)%
ELSE %(OUR KEY WAS LESS THAN OR EQUAL, WHICH?)%
BEGIN %(LESS THAN OR EQUAL)%
LASTLESSOREQUAL = .COMPARESULT; !REMEMBER FOR LATER
IF .INTERVAL NEQ ZERO
THEN %(WE AREN'T THROUGH YET)%
BEGIN %(ADJUST RECORD AND INTERVAL)%
RECORDTOCHECK = .RECORDTOCHECK - ( ( .INTERVAL + 1 ) / 2 ) * .SIZEOFRECORD;
INTERVAL = .INTERVAL / 2
END %(ADJUST RECORD AND INTERVAL)%
ELSE %(INTERVAL IS 0)%
BEGIN %(SUCCESS WITH < OR =)%
IF .RECORDTOCHECK EQL .FIRSTRECORD
THEN RECDESC [ RDLASTRECPTR ] = .RECORDTOCHECK
ELSE RECDESC [ RDLASTRECPTR ] = .RECORDTOCHECK - .SIZEOFRECORD;
RECDESC [ RDRECPTR ] = .RECORDTOCHECK;
IF .COMPARESULT LSS ZERO
THEN SETLSSFLAG ( RECDESC )
ELSE CLRFLAG ( RECDESC [ RDSTATUS ], RDFLGLSS );
GOODRETURN
END %(SUCCESS WITH < OR =)%
END; %(LESS THAN OR EQUAL)%
END %(OF MAIN LOOP)%
END; %(OF SINDEXBKT)%
! FOLLOWPATH
! ===========
! ROUTINE TO FOLLOW THE INDEX PATH FROM A PARTICULAR
! STARTING BUCKET DOWN TO A SPECIFIED LEVEL IN THE
! INDEX STRUCTURE. IN GENERAL, THIS ROUTINE WILL
! BE CALLED WITH THE STARTING BUCKET BEING THE ROOT
! AND WILL SEARCH THE INDEX AND STOP AT THE DATA BUCKET.
! THIS ROUTINE IS CALLED ONLY FROM $PUT.
! INPUT:
! RECDESC RECORD DESCRIPTOR PACKET
! USERPTR ADDRESS OF SEARCH KEY
! USERSIZE SIZE OF SEARCH KEY
! DATABD BUCKET DESC OF DATA LEVEL BUCKET
! OUTPUT:
! TRUE: RECORD POSITION LOCATED
! FALSE: ERROR
! RECORD NOT FOUND
! INPUT PARAMETERS MODIFIED:
! RECORD DESCRIPTOR:
! RECPTR ADDRESS OF DATA RECORD POSITION
! LASTRECPTR ADDRESS OF PREVIOUS RECORD (IF ANY)
! NOTES:
!
! 1. THIS ROUTINE ATTEMPTS TO RECOVER THE CORRECT INDEX
! STRUCTURE WHEN A SYSTEM CRASH CAUSES AN "INEFFICIENT
! TREE". THIS MEANS THAT THE KEY VALUE IN THE INDEX RECORD
! DOES NOT REFLECT THE HIGHEST KEY IN THE DATA BUCKET.
! IN SUCH A CASE, ANY ATTEMPT TO LOCATE A KEY WHICH IS
! BETWEEN THE HIGHEST ACTUAL KEY IN THE DATA BUCKET AND
! WHAT THE INDEX RECORD KEY VALUE IS, MUST SEARCH THE NEXT
! BUCKET IN THE DATA BUCKET CHAIN. THEREFORE, AS THIS
! ROUTINE SEARCHES DOWN THE INDEX, IT MODIFIES THE KEY
! IN THE INDEX RECORD TO REFLECT THE CORRECT VALUE.
GLOBAL ROUTINE FOLLOWPATH ( RECDESC, DATABD ) =
BEGIN
ARGUMENT (RECDESC,BASEADD); ! RECORD DESC
ARGUMENT (DATABD,BASEADD); ! DESC OF DATA
MAP
RECDESC: POINTER,
DATABD: POINTER;
LOCAL
INDEXBD: FORMATS [ BDSIZE ], ! BKT DESC OF INDEX
TEMP;
REGISTER
TEMPAC;
TRACE ('FOLLOWPATH');
%([ FETCH THE ROOT ])%
IF CALLGETROOT (BPT ( RECDESC ),
LCT ( INDEXBD ) ) IS FALSE
THEN
BADRETURN;
%([ DO THIS LOOP UNTIL WE REACH THE DATA LEVEL ])%
REPEAT %(FOREVER)%
BEGIN
%([ FOLLOW THE PATH TO LEVEL 0 ])%
RECDESC [ RDLEVEL ] = DATALEVEL;
RECDESC [ RDRECPTR ] = ZERO; ! START AT TOP
IF CALLFNDREC ( BPT ( RECDESC ),
LCT ( INDEXBD ),
BPT ( DATABD )) IS FALSE
%([ DID WE GET DOWN TO THE DATA? ])%
THEN
RETURN FALSE;
%([ IF WE ARE DATA LEVEL, WE CAN EXIT ])%
IF .RECDESC [ RDLASTLEVEL ] IS DATALEVEL
THEN
GOODRETURN;
IF ( EMPTYFLAG ( RECDESC ) ISON )
THEN %(WE HAVE A BAD FILE)%
BEGIN
FILEPROBLEM ( FE$BEM ); ! EMPTY BUCKET
USEREXIT
END; %(OF IF EMPTY FLAG IS ON)%
%([ AT THIS POINT, WE ARE PAST THE LAST
ENTRY, UPDATE R(LAST) WITH K(S). THIS
SITUATION COULD HAVE BEEN CAUSED BY A
RECORD INSERTION WHICH ABORTED (CRASH,...)
BEFORE THE INDEX WAS COMPLETELY UPDATED.
RMS-20 CAN THEN NOTICE THIS CONDITION AND
CORRECT IT, AS IT IS DOING NOW. ])%
MOVEWORDS ( %(FROM)% .RECDESC [ RDUSERPTR ],
%(TO)% .RECDESC [ RDLASTRECPTR] + IRHDRSIZE,
%(SIZE)% .KDB [ KDBKSZW ] );
%([ AT THIS POINT, WE UPDATED THE INDEX
KEY PART WAY DOWN THE TREE. ])%
RTRACE (%STRING(' RESTARTING FPATH...',%CHAR(13),%CHAR(10)))
END; %(OF REPEAT)%
RMSBUG ( MSGCANTGETHERE )
END; %(OF FOLLOWPATH)%
! FNDREC
! ======
! ROUTINE TO LOCATE A DATA RECORD ( UDR/SIDR) BY SEARCHING THE
! INDEX STRUCTURE. THIS ROUTINE BEGINS ITS SEARCH AT AN
! ARBITRARY BUCKET IN THE INDEX AND SEARCHES DOWNWARD
! UNTIL IT REACHES THE DESIRED LEVEL IN THE TREE.
! IF A BUCKET IS FOUND WITH K(LAST) < K(S), THEN
! WE KNOW THAT THERE MAY HAVE BEEN A CRASH AND THE
! INDEX DIDN'T GET UPDATED FULLY. IN SUCH A CASE, THE
! NEXT BUCKET INTHE CHAIN IS SEARCHED TO SEE IF K(0)
! IN THE NEW BUCKET IS > K(S). IF SO, WE CONTINUE THE
! OPERATION WITH THE CURRENT BUCKET. IF K(0) < K(S), WE
! MUST CONTINUE THE SEARCH AT THE TOP OF THE NEXT
! BUCKET.
!
! WHETHER WE CONTINUE THE SEARCH IN THE NEXT BUCKET IS
! DETERMINED BY THE "HORIZOK" BIT IN THE RECORD DESCRIPTOR FLAG
! FIELD. THIS BIT IS SET ON A $FIND/$GET AND CLEAR ON A $PUT.
! INPUT:
! RECDESC RECORD DESCRIPTOR PACKET
! USERPTR ADDRESS OF SEARCH KEY STRING
! USERSIZE SIZE OF SEARCH KEY STRING
! RECPTR ADDRESS TO START SEARCH (0 = START AT TOP OF BUCKET)
! FLAGS FLAG BITS
! HORIZOK HORIZONTAL SEARCH IS OK
!
! STARTBD BUCKET DESCRIPTOR OF STARTING BUCKET
! ENDBD BUCKET DESCRIPTOR OF ENDING BUCKET (RETURNED)
! OUTPUT STATUS:
! TRUE: SEARCH TERMINATED NORMALLY
! FALSE: ERROR
! DATA BUCKET IS BUSY (BUSY FLAG WILL BE SET)
! INPUT ARGS MODIFIED:
! RECORD DESCRIPTOR
! RECPTR SEARCH TERMINATION ADDRESS
! LASTRECPTR RECORD BEFORE SEARCH TERMINATION
! LASTLEVEL LAST LEVEL SEARCHED
! NOTES:
! 1. THIS ROUTINE STORES THE BUCKET PATH THAT IT SEARCHES
! IN THE "PATH" ARRAY. THE BUCKET # OF THE STARTING
! BUCKET IS STORED ALSO.
!
! 2. EVEN IF THIS ROUTINE EXITS WITH SUCCESS, THE
! "PASTLAST" FLAG MAY BE SET.
GLOBAL ROUTINE FNDREC ( RECDESC, STARTBD, ENDBD ) =
BEGIN
ARGUMENT (RECDESC,BASEADD); ! RCORD DESCRIPTOR
ARGUMENT (STARTBD,BASEADD); ! START BUCKET
ARGUMENT (ENDBD,BASEADD); ! END BUCKET
EXTERNAL
PATH;
MAP
PATH: FORMAT;
MAP
RECDESC: POINTER,
STARTBD: POINTER,
ENDBD: POINTER;
LABEL ITERATION;
LOCAL
BKTNO, !BKT TO READ DURING HORIZ SCAN
!-1 SAYS HAVE FOUND K(S)>K(0)
!0 SAYS LAST BKT IN CHAIN
!N SAYS LOOK HERE FOR K(0)
CURRENTBKTPTR: POINTER, ! PTR TO CURRENT BKT TOP
CURRENTLEVEL,
NBP: POINTER, ! PTR TO NEXT BKT IN CHAIN
NEXTBD: FORMATS[ BDSIZE ], ! BKT DESC OF NEXT BUCKET
CURRENTBUCKET, ! THIS BUCKET NUMBER
SAVERECPTR, ! TEMP STORAGE
SAVELASTRECPTR, ! ...
SAVESTATUS, ! ...
TARGETLEVEL; ! INPUT LEVEL NUMBER
TRACE ('FNDREC');
CHECKEXACTCOUNT;
%([ FOR NOW, WE ALWAYS WANT TO GO TO THE DATA LEVEL ])%
CHECKINPUT ( RECDESC [ RDLEVEL ],EQL,DATALEVEL);
%([ MAKE SURE WE DO A KEY SEARCH ])%
RECDESC [ RDRFA ] = ZERO;
TARGETLEVEL = .RECDESC [ RDLEVEL ]; ! GET LEVEL #
%([ SET UP SOME POINTERS ])%
CURRENTBKTPTR = .STARTBD [ BKDBKTADR ];
%([ MAKE THE INPUT BUCKET THE CURRENT BUCKET ])%
MOVEBKTDESC ( %(FROM)% STARTBD, %(TO)% ENDBD );
%([ THIS IS THE BIG LOOP. IT IS EXECUTED ONCE FOR EACH
LEVEL OF THE INDEX THAT IT SEARCHES. ])%
REPEAT %(FOREVER, OR HOPEFULLY A LITTLE LESS)%
ITERATION: BEGIN
%([ GET LEVEL OF CURRENT BUCKET ])%
CURRENTBKTPTR = .ENDBD [ BKDBKTADR ];
CURRENTLEVEL = .CURRENTBKTPTR [ BHLEVEL ];
%([ STORE THIS VALUE IN THE RECORD DESC ])%
RECDESC [ RDLASTLEVEL ] = .CURRENTLEVEL;
%([ STORE THIS BUCKET NUMBER IN THE PATH ARRAY ])%
CURRENTBUCKET = .ENDBD [ BKDBKTNO ];
PATH [ .CURRENTLEVEL, PATHBKT ] = .CURRENTBUCKET;
LOOKAT (' PREPARING TO SEARCH BKT: ',CURRENTBUCKET );
LOOKAT (' AT LEVEL: ', CURRENTLEVEL );
%([ WE NOW MUST SEARCH THE CURRENT BUCKET ])%
IF ( IF .CURRENTLEVEL IS DATALEVEL
THEN %(WE SHOULD USE THE DATA BUCKET ROUTINE)%
CALLSDATABKT ( %(RECDESC)% BPT ( RECDESC ),
%(BKT)% BPT ( ENDBD ) )
ELSE %(WE SHOULD USE THE INDEX BUCKET ROUTINE)%
CALLSINDEXBKT (%(RD)% BPT ( RECDESC ),
%(BKT)% BPT ( ENDBD ) )) IS FALSE
%([ WHAT HAPPENED? ])%
THEN
BEGIN
%([ WE DID NOT FIND THE RECORD. THE FOLLOWING
COULD BE THE CAUSE:
1. K(LAST) < K(S)
])%
RTRACE (%STRING(' BUCKET SEARCH FAILED...',%CHAR(13),%CHAR(10)));
%([ FIRST, SAVE THE OUTPUT OF THE SEARCH ])%
SAVERECPTR = .RECDESC [ RDRECPTR ];
SAVELASTRECPTR = .RECDESC [ RDLASTRECPTR ];
SAVESTATUS = .RECDESC [ RDSTATUS ];
%([ FETCH THE NEXT BUCKET IN THE CHAIN ])%
%([ IF GTNBKT RETURNS FALSE, THEN THERE WAS NO
NEXT BUCKET...THIS SITUATION IS PERFECTLY OK ])%
IF CALLGTNBKT ( %(CURRENT)% BPT ( ENDBD ),
%(NEXT)% LCT ( NEXTBD ),
%(NO LOCK)% PCI ( FALSE ) ) IS FALSE
THEN GOODRETURN;
%([ WE HAVE NOW GOTTEN THE NEXT BUCKET
IN THE CHAIN. WE MUST CHECK THE FIRST
RECORD TO SEE IF WE SHOULD CONTINUE THE
SEARCH OR STAY WITH THE CURRENT RECORD.
IF HORIZOKFLAG, THEN THE SEARCH CONTINUES REGARDLESS
OF WHETHER K(S) > K(0). IF IT'S OFF,
IMPLYING INSERT MODE, CONTINUE
THE SEARCH ONLY IF INSERT POINT BEYOND K(0). ])%
IF HORIZOKFLAG ( RECDESC ) IS OFF
THEN REPEAT BEGIN %([ COMPARE K(S) WITH K(0) IN THE NEXT BUCKET ])%
RECDESC [ RDRECPTR ] = -1; ! FLAG 1 REC SEARCH
IF .CURRENTLEVEL IS DATALEVEL
THEN
BEGIN
RECDESC [ RDRFA ] = ZERO; ! KEY SEARCH
CALLSDATABKT ( BPT ( RECDESC ),
LCT ( NEXTBD ) )
END %(OF THIS IS A DATA BUCKET)%
ELSE %( THIS IS AN INDEX BUCKET )%
CALLSINDEXBKT ( BPT ( RECDESC ),
LCT ( NEXTBD ) );
%([ IS K(S) < K(0)? BUT 1ST DET IF KEY THERE
IF NONE THERE, ALSO CHK IF EOF ])%
BKTNO = -1; !PRESUME VALID ENTRY SEEN
IF PASTLASTFLAG(RECDESC) ISON !ANY KEY IN BKT
THEN BEGIN !NO
NBP = .NEXTBD[BKDBKTADR]; !PT AT BKT LAST READ
IF CHKFLAG(NBP[BHFLAGS], BHFLGEND) IS OFF
THEN BKTNO = .NBP[BHNEXTBKT]
!SET BKT TO READ
ELSE BKTNO = 0; !EOF
END;
IF LSSFLAG ( RECDESC ) ISON OR .BKTNO EQL 0
THEN %(INSERT PT FND BY KEY COMP OR EOF, AND
WE SHOULD RELEASE NEXT BKT & USE OLD 1)%
BEGIN
%([ YES ])%
RTRACE (%STRING(' K(S)<K(0)',%CHAR(13),%CHAR(10)));
CALLPUTBKT ( %(NO UPDATE)% PCI ( FALSE),
%(BKT)% LCT ( NEXTBD ) );
%([ RESTORE OUR SEARCH KEYS ])%
RECDESC [ RDRECPTR ] = .SAVERECPTR;
PATH [ .CURRENTLEVEL,PATHOFFSET ] = .SAVERECPTR - .CURRENTBKTPTR;
RECDESC [ RDLASTRECPTR ] = .SAVELASTRECPTR;
RECDESC [ RDSTATUS ] = .SAVESTATUS;
SETPASTLASTFLAG ( RECDESC );
GOODRETURN;
END; %(OF IF K(S) < K(0) )%
IF .BKTNO LSS 0 THEN EXITLOOP; !K(S)>=K(0)
! NO KEYS IN BKT CHAINED TO, PICK UP NEXT 1
CALLPUTBKT ( %(NO UPDATE)% PCI ( FALSE),
%(BKT)% LCT ( NEXTBD ) );
IF $CALL (GETBKT, .BKTNO, !BKT TO READ
.KDB[KDBDBKZ], !ALW DATA BKT
FALSE, NEXTBD) IS FALSE
THEN BADRETURN;
END; %(OF IF HORIZOKFLAG IS OFF & LOOP)%
%([ NO...K(S) >= K(0) OR HORIZONTAL-OK FLAG
WAS ON. WE SHOULD RESTART
THE SEARCH AT THE TOP OF NEXT BUCKET ])%
RECDESC [ RDRECPTR ] = ZERO; ! START AT TOP
CALLPUTBKT ( %(NO UPDATE)% PCI ( FALSE),
%(BKT)% BPT ( ENDBD ) );
%([ MAKE THE NEXT BUCKET THE CURRENT ONE ])%
MOVEBKTDESC ( %(FROM)% NEXTBD, %(TO)% ENDBD );
%([ EXIT FROM THE LOOP AND START AT TOP AGAIN ])%
LEAVE ITERATION
END; %(OF IF SEARCH BUCKET FAILED)%
%([ WE HAVE FOUND A RECORD WITH KEY >= K(S). ])%
RTRACE (%STRING(' FOUND TARGET RECORD',%CHAR(13),%CHAR(10)));
%([ STORE THE OFFSET INTO THE CURRENT BUCKET IN THE PATH ARRAY ])%
PATH [ .CURRENTLEVEL, PATHOFFSET ] = .RECDESC [ RDRECPTR ] - .CURRENTBKTPTR;
%([ IS THIS THE LEVEL WE WANTED? ])%
IF .CURRENTLEVEL IS .TARGETLEVEL
THEN
GOODRETURN;
%IF DBUG %THEN
IF .CURRENTLEVEL LSS .TARGETLEVEL THEN rmsbug ( MSGLEVEL);
%FI
%([ GET THE BUCKET AT THE NEXT LEVEL IN THE TREE ])%
SAVESTATUS = CALLGTBKTPTR ( %(RD)% BPT ( RECDESC ),
%(CURRENT)% BPT ( ENDBD ),
%(NEXT)% LCT ( NEXTBD ) );
%([ WE CAN NOW RELEASE THE CURRENT BUCKET ])%
CALLPUTBKT ( %(NO UPDATE)% PCI ( FALSE ),
%(BKT)% BPT ( ENDBD ) );
%([ IF WE COULDN'T GET THE NEXT BUCKET, THEN EXIT ])%
IF .SAVESTATUS IS FALSE THEN BADRETURN;
%([ MAKE SURE WE START AT TOP OF BUCKET ])%
RECDESC [ RDRECPTR ] = ZERO;
%([ MAKE THE NEXT BKT TO BE THE CURRENT ONE ])%
MOVEBKTDESC ( %(FROM)% NEXTBD, %(TO)% ENDBD );
END; %(OF REPEAT LOOP)%
RMSBUG ( MSGCANTGETHERE )
END; %(OF FNDREC)%
! IDXUPDATE
! =========
! THIS ROUTINE IS RESPONSIBLE FOR ALL INDEX MODIFICATIONS WHICH
! MUST BE DONE WHEN A NEW DATA RECORD INSERTION
! CAUSES THE DATA BUCKET TO SPLIT. THIS ROUTINE
! ITERATIVELY TRACES UP THE TREE.
! THEN, IT INSERTS OR MODIFIES THE INDEX
! RECORDS TO REFLECT THE SPLIT AT THE NEXT
! LOWER LEVEL. IF THIS INDEX RECORD INSERTION
! ALSO CAUSES A BUCKET SPLIT, THE PROCEDURE
! IS REPEATED UP UNTIL POTENTIALLY A NEW
! ROOT IS GENERATED. THE DATA BUCKET IS NOT
! UNLOCKED IN THIS ROUTINE.
! TERMINOLOGY USED IN THIS ROUTINE
! R(NEW) = THE NEW INSERTED DATA RECORD
! R(LOW) = SET OF RECORDS WITH KEYS < R(NEW)
! R(HIGH) = SET OF RECORDS WITH KEY > R(NEW)
! K(HIGH) = NEW HIGH KEY FOR ORIGINAL BUCKET WHICH SPLIT
! INPUTS
! RECORD DESCRIPTOR
! LASTRECPTR => LAST DATA RECORD ( K(HIGH) ) OF ORIGINAL DATA BUCKET
! USERPTR => USER KEY STRING
! USERSIZE FULL KEY STRING SIZE
! BUCKET DESCRIPTOR OF ORIGINAL DATA BUCKET
! BUCKET DESCRIPTOR OF SPLIT-BUCKET (CONTAIN R-HIGH)
! BUCKET DESCRIPTOR OF 2ND SPLIT-BUCKET (IF 3-BKT SPLIT)
! OUTPUT
! TRUE: OK
! FALSE: ERROR
! NO PAGES LEFT FOR SPLIT OF INDEX
! NOTES:
!
! 1. SEE THE NOTES UNDER "INSRTIRECORD" FOR A DISCUSSION
! OF THE PLACEMENT OF THE NEW HIGH-KEY VALUE FOR
! A BUCKET SPLIT.
!
! 2. NOTE THAT THE BUCKET WHICH CONTAINS R-HIGH (SPLITBD1)
! HAS ALREADY BEEN RELEASED WHEN THIS ROUTINE IS ENTERED.
! THUS, ONLY THE BUCKET NUMBER IS USED FROM THE BUCKET
! DESCRIPTOR...THE ACTUAL BUCKET ITSELF MUST NOT BE
! ACCESSED IN ANY WAY.
!
! 3. THERE ARE THREE CONDITIONS WHICH MAY ARISE WHEN THE INDEX
! RECORD IS CHECKED IN THIS ROUTINE:
!
! A) THE SEARCH KEY (OF NEW RECORD) IS .LSS. THE KEY OF THE
! INDEX RECORD. THIS IS BY FAR THE USUAL CASE.
! B) THE SEARCH KEY IS .EQL. TO INDEX KEY. THIS IS CAUSED BY
! A SPLIT OF A BUCKET WITH A LOT OF A SINGLE DUP KEY.
! THUS, THE OLD BUCKET STILL HAS A DUP FOR THE HI-KEY
! AND THE NEW BUCKET CONTAINS ONLY THE SAME DUP KEYS.
! B) THE SEARCH KEY IS .GTR. THE INDEX KEY. THIS IS VERY
! UNUSUAL AND IS CAUSED WHEN THE BUCKET WHICH IS BEING
! SPLIT IS NOT THE SAME DATA BUCKET FOUND WHEN THE SEARCH
! TERMINATED AT THE DATA LEVEL (E.G., A SERIES OF DUPS
! HAD TO BE PASSED TO GET TO THE INSERTION POINT).
! IN THIS CASE, WE REALLY NEED TO BE AT THE INDEX RECORD
! WHICH REFLECT THE NEW KI-KEY VALUE OF THE SPLIT BUCKET.
! THUS, WE WILL CALL ADJIPTR TO FIND THE NEW INDEX RECORD.
! ARGUMENTS MODIFIED:
!
! RECORD DESCRIPTOR
! <NONE>
!
! BUCKET DESCRIPTOR
! <NONE>
!
! ROUTINES CALLED:
! ALLOCBKT
! FINDIBUCKET
! GETBUCKET
! GETIDB
GLOBAL ROUTINE IDXUPDATE ( RECDESC, DATABD, SPLITBD1, SPLITBD2 ) =
BEGIN
ARGUMENT (RECDESC,BASEADD);
ARGUMENT (DATABD,BASEADD);
ARGUMENT (SPLITBD1,BASEADD);
ARGUMENT (SPLITBD2,BASEADD);
MAP
RECDESC: POINTER,
DATABD: POINTER,
SPLITBD1: POINTER,
SPLITBD2: POINTER;
LOCAL
INDEXBD: FORMATS[ BDSIZE ], ! ROOT BUCKET DESC
ARRAYINDEX, ! USED TO INDEX INTO PATH
NEXTINDEXBUCKET, ! NEXT BKT TO GET
INDEXBUCKETSIZE, ! GUESS!
ORIGINALBD: FORMATS[ BDSIZE ],
IRECORDPTR: POINTER, ! PTR TO CURRENT INDEX RECORD
SAVEDUSERPTR, ! TEMP STORAGE FOR SEARCH KEY
BKTONNEXTLEVEL;
EXTERNAL ROUTINE
CKEYKK, ! COMPARE KEYS
ADJIPTR; ! ADJUST INDEX POINTER
EXTERNAL
PATH; ! ARRAY THAT HOLDS BKT PATH
MAP
PATH: FORMAT;
TRACE ( 'IDXUPDATE' );
%([ MOVE THE BUCKET DESCRIPTOR SO IT WON'T GET CLOBBERED ])%
MOVEBKTDESC ( %(FROM)% DATABD, %(TO)% ORIGINALBD );
INDEXBUCKETSIZE = .KDB [ KDBIBKZ ]; ! SAVE TIME LATER
%([ WE ARE CURRENTLY POSITIONED AT LEVEL 1 OF THE INDEX.
WE WILL CONTINUE TO INSERT INDEX RECORDS UNTIL EITHER
WE REACH THE ROOT OF NO INDEX BUCKET SPLITTING OCCURS.
WE HAVE THE FOLLOWING VALUES:
1. ORIGINALBD BKT WHICH WAS SPLIT
2. SPLITBD1 BKT WHICH CONTAINS R(HIGH)
3. SPLITBD2 BKT WHICH CONTAIN R(NEW)
(ONLY IF DATA IS SPLITTING AND
IT WAS A 3-BKT SPLIT)
4. INDEXBD INDEX BKT WHICH WILL CONTAIN
THE NEW RECORD
])%
%([ START AT LEVEL 1 ])%
ARRAYINDEX = SEQSETLEVEL;
%([ THIS IS THE MAIN INDEX UPDATE LOOP ])%
UNTIL IDXUPDATEFLAG ( RECDESC ) IS OFF
DO %(THIS LOOP)%
BEGIN
%([ GET THE BUCKET DIRECTLY ABOVE US ])%
BKTONNEXTLEVEL = .PATH [ .ARRAYINDEX, PATHBKT ];
%([ LOCATE THE BUCKET ])%
IF CALLGETBKT ( %(BKT #)% LCI ( BKTONNEXTLEVEL ),
%(SIZE)% LCI ( INDEXBUCKETSIZE ),
%(NO LOCK)% PCI ( FALSE ),
%(BKT)% LCT ( INDEXBD ) ) IS FALSE
%([ DID WE GET IT? ])%
THEN
RETURN FALSE;
%([ AT THIS POINT, WE HAVE MAPPED IN THE NEXT HIGHER
BUCKET IN THE INDEX STRUCTURE. WE CAN NOW COMPUTE THE
ADDRESS OF THE INDEX ENTRY WHICH GOT US TO THE
CURRENT LEVEL BECAUSE WE HAVE THE BUCKET OFFSET
STORED IN THE PATH ARRAY. ])%
IRECORDPTR = (RECDESC [ RDRECPTR ] = .PATH [ .ARRAYINDEX, PATHOFFSET ] + .INDEXBD [ BKDBKTADR ]);
%([ WE NOW MUST DETERMINE IF WE SHOULD, IN FACT, ACTUALLY
INSERT A NEW INDEX RECORD. WE DON'T WANT TO DO THIS IF
THE OLD INDEX KEY IS THE SAME AS THE NEW HIGH-KEY VALUE
IN THE BUCKET WHICH SPLIT. SUCH A CASE COULD BE CAUSED
BY A SERIES OF DUPS WHICH GOT MOVED TO A NEW BUCKET. ])%
SAVEDUSERPTR = .RECDESC [ RDUSERPTR ]; ! SAVE KEY PTR
RECDESC [ RDUSERPTR ] = .RST [ RSTKEYBUFF ] + (.FST [ FSTKBFSIZE ] / 2 );
INC ( IRECORDPTR, IRHDRSIZE ); ! BUMP PTR TO INDEX KEY
%([ COMPARE THE INDEX KEY TO THE NEW HIGH KEY ])%
IF CALLCKEYKK ( %(NEW HIGH KEY)% BPT ( RECDESC ),
%(INDEX KEY)% LPT ( IRECORDPTR ) ) IS FALSE
%([ IF WE FAIL, IT MEANS THERE WAS A KEY IN THE BUCKET
WHICH WAS GTR THAN THE INDEX KEY. THIS IS CAUSED BY
A SPLIT IN A DATA BUCKET WHICH WAS NOT THE FIRST BUCKET
SEARCHED WHEN THE RECORD POSITION WAS INITIALLY LOCATED. ])%
%([ ***** NOTE *****
THIS ENTIRE OPERATION OF COMPARING THE KEY OF THE
OLD INDEX RECORD TO THE NEW HI-KEY OF THE DATA BUCKET
WHICH WAS SPLIT IS NECESSARY IF BUCKET SPLITS CAN BE
ANYWHERE IN THE BUCKET, REGARDLESS OF WHETHER THERE
ARE DUPLICATES PRESENT OR NOT. HOWEVER, THE BUCKET
SPLIT ALGORITHM CURRRENTLY (MAY, 1977) DIVIDES THE
BUCKET EITHER BEFORE OR AFTER THE INSERTED RECORD IF
DUPLICATES ARE ALLOWED (PRIMARY ONLY). THUS, IT IS
IMPOSSIBLE FOR A BUCKET TO BE SPLIT IF THAT BUCKET IS
<<<NOT>>> THE BUCKET WHERE THE INDEX SEARCH TERMINATED
(I.E., IT IS NOT IN A LIST OF BUCKETS WHICH ARE NOT
CONTAINED IN THE INDEX). THEREFORE, THIS NEXT CHECK
WILL NEVER BE EXECUTED. THE CODE IS LEFT IN FOR
RELIABILITY AND DOCUMENTATION. ])%
THEN
CALLADJIPTR ( BPT ( RECDESC ),
LCT ( INDEXBD ) )
ELSE %(THE HI-KEY IS .LEQ. THE INDEX KEY)%
BEGIN
%([ IF THE LESS-THAN FLAG IS ON, WE ARE OK ])%
IF LSSFLAG ( RECDESC ) IS OFF
THEN
BEGIN
CALLPUTBKT ( %(NO)% PCI ( FALSE ),
%(BKT)% LCT ( INDEXBD ) );
GOODRETURN
END %(OF IF LSSFLAG IS OFF)%
END; %(OF ELSE)%
RECDESC [ RDUSERPTR ] = .SAVEDUSERPTR; ! RESTORE PTR
%([ AT THIS POINT, RECPTR POINTS TO THE PLACE TO INSERT
THE NEW INDEX RECORD. WE WILL INSERT IT AND
INSERTIRECORD WILL RETURN UPDATED BUCKET DESCRIPTORS
IF A FURTHER INDEX UPDATE IS NEEDED. ])%
IF CALINSRTIRECORD ( %(RD)% BPT ( RECDESC ),
%(BKT)% LCT ( INDEXBD ),
%(OLD BKT)% LCT ( ORIGINALBD ),
%(SPLIT)% BPT ( SPLITBD1 ),
%(SPLIT)% BPT ( SPLITBD2 ) ) IS FALSE
%([ WHAT HAPPENED? ])%
THEN
RETURN FALSE;
%([ BUMP THE LEVEL NUMBER THAT WE ARE AT ])%
INC ( ARRAYINDEX, 1 )
END; %(OF UNTIL IDXUPDATE FLAG IS OFF)%
%([ AT THIS POINT, WE HAVE DONE ALL OUR UPDATING ])%
GOODRETURN
END; %(OF IDXUPDATE)%
! GTBKTPTR
! ========
! ROUTINE TO GET THE NEXT BUCKET DOWNWARD IN THE INDEX.
! THIS ROUTINE ASSUMES THAT WE ARE POSITIONED AT
! THE CURRENT INDEX RECORD. IT FETCHES THE BUCKET
! # OF THE NEXT BUCKET IN THE INDEX AND MAPS IT IN.
! INPUT:
! RECDESC RECORD DESCRIPTOR
! RECPTR ADDRESS OF INDEX RECORD
! THISBD BKT DESCRIPTOR OF CURRENT BUCKET
! NEXTBD BKT DESCRIPTOR OF NEXT BKT (RETURNED)
! OUTPUT:
! TRUE: BUCKET FOUND AND MAPPED
! FALSE: ERROR
! NO MORE MEMORY
! NOTES:
! 1. THIS ROUTINE WILL NEVER LOCK ANY
! BUCKETS, EITHER INDEX OR DATA.
! ROUTIES CALLED:
! GETBKT
GLOBAL ROUTINE GTBKTPTR ( RECDESC, THISBD, NEXTBD ) =
BEGIN
ARGUMENT (RECDESC,BASEADD); ! RECORD PACKET
ARGUMENT (THISBD,BASEADD); ! CURRENT BKT
ARGUMENT (NEXTBD,BASEADD); ! NEXT ONE
MAP
RECDESC: POINTER,
THISBD: POINTER,
NEXTBD: POINTER;
REGISTER
ACPTR: POINTER;
LOCAL
NEXTBUCKET, ! NEXT BUCKET IN THE INDEX
LOCKFLAG, ! TELLS IF WE WILL LOCK IT
BUCKETSIZE;
TRACE ('GTBKTPTR');
CHECKEXACTCOUNT;
%([ FIND OUT THE BUCKET # WE NEED TO GET ])%
ACPTR = .RECDESC [ RDRECPTR ];
NEXTBUCKET = .ACPTR [ IRBUCKET ];
%([ FIND OUT THE LEVEL OF THIS BUCKET ])%
ACPTR = .THISBD [ BKDBKTADR ];
BUCKETSIZE = .KDB [ KDBIBKZ ]; ! ASSUME INDEX
LOCKFLAG = FALSE; ! SAME
IF .ACPTR [ BHLEVEL ] IS SEQSETLEVEL
THEN %(WE ARE GOING TO DATA LEVEL)%
BUCKETSIZE = .KDB [ KDBDBKZ ];
%([ GET THE BUCKET AND RETURN ])%
RETURN CALLGETBKT (%(NUMBER)% LCI ( NEXTBUCKET ),
%(SIZE)% LCI ( BUCKETSIZE ),
%(LOCK)% LCI ( LOCKFLAG ),
%(DESC)% BPT ( NEXTBD ) );
END; %(OF GTBKTPTR)%
! GTNBKT
! ======
! ROUTINE TO FETCH THE NEXT BUCKET IN THE HORIZONTAL CHAIN
! OF THE CURRENT LEVEL OF THE INDEX STRUCTURE.
! IF THERE IS A NEXT BUCKET, THIS ROUTINE WILL MAP AND
! LOCK IT (IF IT IS A DATA BUCKET). IF THERE IS NO
! NEXT BUCKET, THIS ROUTINE WILL EXIT WITH AN ERROR
! CONDITION.
! INPUT:
! THISBD BKT DESCRIPTOR OF CURRENT BUCKET
! NEXTBD BKT DESCRIPTOR OF NEXT BUCKET ( RETURNED)
! LOCKFLAG FLAG TO DETERMINE IF WE SHOULD LOCK NEXT BUCKET
! OUTPUT:
! TRUE: OK
! FALSE: ERROR
! BUCKET WAS BUSY (BUSY FLAG WILL BE SET)
! NO NEXT BUCKET
! ROUTINES CALLED:
! GETBKT
GLOBAL ROUTINE GTNBKT ( THISBD, NEXTBD, LOCKFLAG ) =
BEGIN
ARGUMENT (THISBD,BASEADD); ! CURRENT BKT
ARGUMENT (NEXTBD,BASEADD); ! NEXT ONE IN LINE
ARGUMENT (LOCKFLAG,REFERENCE); ! FLAG FOR LOCKING
MAP
THISBD: POINTER,
NEXTBD: POINTER;
LOCAL
THISBKTPTR: POINTER, ! BUCKET POINTER
SAVEDSTATUS, ! SAVE THE RESULTS OF GETBKT HERE
NEXTBUCKET, ! BKT # OF NEXT BKT
BUCKETSIZE; ! SIZE OF NEXT BKT
TRACE ('GTNBKT');
CHECKEXACTCOUNT;
%([ GET A POINTER TO THE CURRENT BUCKET ])%
THISBKTPTR = .THISBD [ BKDBKTADR ];
%([ IS THIS THE END OF THE BUCKET CHAIN? ])%
IF CHKFLAG ( THISBKTPTR [ BHFLAGS ], BHFLGEND ) ISON
THEN %(THIS IS THE END)%
BADRETURN;
%([ THERE IS ANOTHER BUCKET IN THE CHAIN...FIND IT ])%
NEXTBUCKET = .THISBKTPTR [ BHNEXTBKT ];
BUCKETSIZE = .KDB [ KDBIBKZ ]; ! SAME
IF .THISBKTPTR [ BHBTYPE ] IS BTYPEDATA
THEN
BUCKETSIZE = .KDB [ KDBDBKZ ];
%([ MAP (AND LOCK) THE BUCKET ])%
RETURN CALLGETBKT ( %(BKT)% LCI ( NEXTBUCKET ),
%(SIZE)% LCI ( BUCKETSIZE ),
%(LOCK)% RLCI ( LOCKFLAG ),
%(BD)% BPT ( NEXTBD ) );
END; %(OF GTNBKT)%
! SPTINDEX
! ========
! ROUTINE TO SPLIT AN INDEX BUCKET DURING A RECORD INSERTION.
! THIS ROUTINE TAKES THE CURRENT INDEX BUCKET AND SPLITS
! THE RECORDS IN IT INTO TWO GROUPS. ONE GROUP OF RECORDS
! IS MOVED TO A NEW BUCKET; THE OTHER GROUP REMAINS IN THIS
! BUCKET.
! INPUT:
! RECDESC RECORD DESCRIPTOR PACKET
! RECPTR ADDRESS IN INDEX BUCKET TO INSERT RECORD
! LENGTH AMOUNT OF SPACE REQUIRED FOR NEW IDX RECORDS
!
! INDEXBD BKT DESCRIPTOR OF INDEX BUCKET TO BE SPLIT
! NEWINDEXBD BKT DESCRIPTOR OF NEW INDEX BKT (RETURNED)
! OUTPUT STATUS:
! TRUE: OK
! FALSE: ERROR
! NO MORE BUCKETS
! INPUT ARGS MODIFIED:
! RECORD DESCRIPTOR
! RECPTR ADDRESS TO INSERT NEW RECORDS
! LASTRECPTR ADDRESS OF LAST RECORD IN INDEX BKT
! WHICH SPLIT
!
! ROUTINES CALLED:
! ALCBKT
! NOTES:
! 1. THIS ROUTINE ONLY SPLITS THE INDEX BUCKET. IT
! DOES NOT LEAVE ROOM FOR THE INDEX RECORD, NOR DOES
! IT ADJUST THE "NEXT-BYTE" POINTER OF THE BUCKET
! TO ACCOUNT FOR THE INDEX RECORD WHICH IS TO BE
! INSERTED.
!
! 2. THIS ROUTINE DOES NOT MOVE THE KEY OF THE LAST RECORD
! IN THE OLD BUCKET BECAUSE THE KEY-BUFFER CURRENTLY
! CONTAINS THE NEW HIGH-KEY VALUE OF THE NEXT LOWER LEVEL.
!
! 3. THE ALGORITHM FOR SPLITTING AN INDEX BUCKET IS VERY
! SIMILAR TO THE SAME ALGORITHM FOR SPLITTING A DATA
! BUCKET. THAT IS, THE NEW RECORD(S) ARE PLACE WITH
! R-LOW IF POSSIBLE AND AS MANY R-HIGH RECORDS AS WILL
! FIT WILL ALSO STAY IN THE OLD BUCKET. IF THE NEW
! RECORD(S) WILL NOT FIT WITH R-LOW, THEN IT(THEY)
! ARE MOVED TO THE NEW BUCKET COMPLETELY WITH R-HIGH.
! THIS ALGORITHM HAS THE EFFECT THAT INSERTING RECORDS
! AT THE BOTTOM OF THE BUCKET WILL TEND TO FILL THE
! OLD BUCKET MORE THAN THE NEW BUCKET. HOWEVER, THE
! ALTERNATIVE IS BACKWARD SCANNING OF THE INDEX RECORDS
! IN R-LOW IN ORDER TO MAXIMIZE PRECISELY THE SPLIT
! LOCATION. SUCH A TECHNIQUE IS NOT JUDGED TO BE WORTH
! THE EXTRA MANIPULATIONS REQUIRED TO SUPPORT IT.
! NOTE THAT THIS ALGORITHM ASSUMES THAT AT LEAST
! THREE INDEX RECORDS WILL FIT IN AN INDEX BUCKET.
! IF THIS EVER BECOMES NOT TRUE, THEN EXTRA
! MACHINATIONS WILL BE REQUIRED BY THIS ROUTINE.
GLOBAL ROUTINE SPTINDEX ( RECDESC, INDEXBD, NEWINDEXBD ) =
BEGIN
ARGUMENT (RECDESC,BASEADD); ! REC DESCRIPTOR
ARGUMENT (INDEXBD,BASEADD); ! OLD INDEX BKT
ARGUMENT (NEWINDEXBD,BASEADD); ! NEW BKT
MAP
RECDESC: POINTER,
INDEXBD: POINTER,
NEWINDEXBD: POINTER;
LOCAL
TOTALSIZE, ! AMOUNT OF SPACE REQUIRED FOR NEW RECORDS
SIZEOFIDXRECORD, ! SIZE OF ONE INDEX RECORD
AMOUNTTOMOVE, ! AMOUNT OF STUFF TO MOVE OUT
THISLEVEL, ! LEVEL OF THIS INDEX BUCKET
BKTFLAGS, ! FLAGS OF CURRENT INDEX BKT
NEWBUCKET, ! BKT # OF NEW INDEX BKT
NEXTFREEBYTE, ! TEMP
SIZELOW, ! SIZE OF R-LOW RECORDS
SPACENEEDED, ! SIZE OF NEW RECORD(S)
AMOUNTOFDATA, ! AMOUNT OF RECORD SPACE USED UP
MAXDATASIZE, ! MAX SPACE AVAILABLE IN EMPTY BKT
OLDINDEXPTR: POINTER, ! PTR TO OLD INDEX BKT
ENDPTR: POINTER, ! PTR TO END OF BUCKET
NEWINDEXPTR: POINTER; ! PTR TO NEW INDEX BKT
REGISTER
TPTR: POINTER, ! TEMP POINTER
SPLITPTR: POINTER, ! PTR TO PLACE TO SPLIT
INSERTPTR: POINTER; ! PLACE TO INSERT RECORD
TRACE ('SPTINDEX');
CHECKEXACTCOUNT;
%([ GET THE FLAGS AND LEVEL NUMBER OF CURRENT BUCKET ])%
OLDINDEXPTR = .INDEXBD [ BKDBKTADR ];
THISLEVEL = .OLDINDEXPTR [ BHLEVEL ];
BKTFLAGS = .OLDINDEXPTR [ BHFLAGS ] AND BHFLGEND; ! LEAVE END BIT
NEXTFREEBYTE = .OLDINDEXPTR [ BHNEXTBYTE ];
%([ ALLOCATE A NEW INDEX BUCKET ])%
IF CALLALCBKT (%(TYPE)% PCI ( BTYPEINDEX ),
%(FLAGS)% LCI ( BKTFLAGS ),
%(LEVEL)% LCI ( THISLEVEL ),
%(BKT)% BPT ( NEWINDEXBD )) IS FALSE
%([ COULD WE DO IT? ])%
THEN
RETURN FALSE;
%([ GET PTR TO THE NEW BUCKET ])%
NEWINDEXPTR = .NEWINDEXBD [ BKDBKTADR ];
%([ WE MUST NOW COMPUTE HOW MUCH OF THIS BUCKET SHOULD BE
MOVED TO THE NEW BUCKET. THE ALGORITHM IS DESCRIBED
ABOVE ])%
%([ COMPUTE TOTAL SIZE OF AN INDEX RECORD ])%
SIZEOFIDXRECORD = .KDB [ KDBKSZW ] + IRHDRSIZE;
LOOKAT (' SIZE-OF-REC: ', SIZEOFIDXRECORD );
%([ NOW, WE NEED TO FIGURE OUT HOW WE WANT TO SPLIT THIS BUCKET ])%
INSERTPTR = .RECDESC [ RDRECPTR ]; ! START AT INSERTION POINT
SIZELOW = .INSERTPTR - .OLDINDEXPTR - BHHDRSIZE; ! SIZE OF R-LOW
LOOKAT (' SIZE-LOW: ', SIZELOW );
SPACENEEDED = .RECDESC [ RDLENGTH ]; ! SPACE WE NEED
MAXDATASIZE = .KDB [ KDBIBKZ ] ^ B2W ; ! FIND OUT HOW MUCH SPACE WE HAVE
%([ IF THE USER SPECIFIED HIS OWN LOAD FILLS, WE MUST USE
THEM. ])%
IF CHKFLAG ( RAB [ RABROP ], ROPLOA ) ISON
THEN
MAXDATASIZE = .KDB [ KDBIFLOFFSET ];
DEC ( MAXDATASIZE, BHHDRSIZE ); ! ACCOUNT FOR HEADER
LOOKAT (' MAX-DATA-SIZE: ', MAXDATASIZE );
SPLITPTR = .INSERTPTR; ! ASSUME SPLIT HERE
%([ CAN WE FIT THE NEW RECORD(S) WITH R-LOW? ])%
IF ( .SIZELOW + .SPACENEEDED ) LEQ .MAXDATASIZE
THEN %(THE NEW IDX RECORD WILL GO WITH R-LOW)%
BEGIN
RTRACE (%STRING(' IDX REC STAYS WITH R-LOW...',%CHAR(13),%CHAR(10)));
INC ( SIZELOW, .SPACENEEDED ); ! BUMP COUNTER
%([ LOOP OVER ALL THE RECORDS FROM HERE DOWN AND
KEEP AS MANY OF THEM AS POSSIBLE (UNTIL WE GO
OVER ONE-HALF OF THE BUCKET ])%
AMOUNTOFDATA = .OLDINDEXPTR [ BHNEXTBYTE ] - BHHDRSIZE
+ .SPACENEEDED;
UNTIL .SIZELOW GTR ( .AMOUNTOFDATA ^ DIVIDEBY2LSH )
DO %(THIS LOOP)%
BEGIN
INC ( SPLITPTR, .SIZEOFIDXRECORD );
INC ( SIZELOW, .SIZEOFIDXRECORD ); ! BUMP CTR
LOOKAT ( ' BUMP SPLITPTR TO: ', SPLITPTR );
LOOKAT ( ' BUMP SIZELOW TO: ', SIZELOW );
END %(OF SCANNING R-HIGH)%
END %(OF IF R-NEW WILL FIT WITH R-LOW)%
ELSE %(THE NEW RECORD MUST BE MOVED OUT WITH R-HIGH)%
INSERTPTR = .NEWINDEXPTR + BHHDRSIZE; ! RESET POINTER
%([ FIGURE OUT HOW MUCH MUST GO ])%
AMOUNTTOMOVE = .OLDINDEXPTR [ BHNEXTBYTE ] + .OLDINDEXPTR - .SPLITPTR;
LOOKAT (' AMT-TO-MOVE:', AMOUNTTOMOVE );
%IF DBUG %THEN
IF .AMOUNTTOMOVE LSS ZERO THEN RMSBUG ( MSGCOUNT );
%FI
%([ MOVE THE BOTTOM OF THE INDEX OUT ])%
IF .AMOUNTTOMOVE ISNT ZERO
THEN
MOVEWORDS ( %(FROM)% .SPLITPTR,
%(TO)% .NEWINDEXPTR + BHHDRSIZE,
%(SIZE)% .AMOUNTTOMOVE );
%([ RESET BUCKET HEADER DATA ])%
DEC ( OLDINDEXPTR [ BHNEXTBYTE ], .AMOUNTTOMOVE );
NEWINDEXPTR [ BHNEXTBYTE ] = BHHDRSIZE + .AMOUNTTOMOVE;
NEWINDEXPTR [ BHNEXTBKT ] = .OLDINDEXPTR [ BHNEXTBKT ];
OLDINDEXPTR [ BHNEXTBKT ] = .NEWINDEXBD [ BKDBKTNO ];
CLRFLAG ( OLDINDEXPTR [ BHFLAGS ], BHFLGEND ); ! CLEAR END FLAG
%([ LET'S SEE THE NEW HEADERS ])%
%IF DBUG %THEN
BUGOUT (%STRING('DUMP OF OLD BKT HEADER: ',%CHAR(13),%CHAR(10)));
CALLDUMPHEADER ( LPT ( OLDINDEXPTR ) );
BUGOUT (%STRING('DUMP OF NEW INDEX BKT HDR:',%CHAR(13),%CHAR(10)));
CALLDUMPHEADER ( LPT ( NEWINDEXPTR ) );
%FI
%([ RESET THE ADDRESS WHERE THE NEW RECORD WILL GO ])%
RECDESC [ RDRECPTR ] = .INSERTPTR;
GOODRETURN
END; %(OF SPTINDEX)%
! INSRTIRECORD
! ============
! ROUTINE TO INSERT A NEW RECORD INTO AN INDEX BUCKET.
! THIS ROUTINE IS CALLED WHEN EITHER AN INDEX OR
! A DATA BUCKET HAS SPLIT AND WE NEED TO CREATE A
! NEW INDEX ENTRY FOR THE SPLIT BUCKET.
! INPUT:
! RECDESC RECORD DESCRIPTOR PACKET
! RECPTR ADDRESS WHERE NEW RECORD IS TO BE INSERTED
! USERPTR ADDRESS OF SERCH KEY
! USERSIZE SIZE OF SEARCH KEY
! COUNT # OF NEW BKTS IN THE SPLIT (1 FOR INDEX,
! 1 OR 2 FOR DATA)
!
! INDEXBD BUCKET DESCRIPTOR FOR INDEX BUCKET
! ORIGINALBD BUCKET DESCRIPTOR OF BUCKET WHICH SPLIT
! SPLITBD1 BUCKET DESCRIPTOR OF NEW BUCKET # 1
! SPLITBD2 BUCKET DESCRIPTOR OF NEW BUCKET # 2
! OUTPUT STATUS:
! TRUE: INDEX UPDATE OK
! FALSE: ERROR
! COULDN'T MODIFY INDEX
! INPUT ARGS MODIFIED:
! RECDESC:
! <NONE>
! ORIGINALBD:
! THIS WILL CONTAIN SAME CONTENTS AS INDEXBD
! NOTES:
!
! 1. DATA SPLITS MAY INVOLVE 2 EXTRA BUCKETS. INDEX SPLITS
! ONLY REQUIRE 1 EXTRA BUCKET.
!
! 2. ON OUTPUT, THE INPUT BUCKET DESCRIPTOR OF THE ORIGINALBD
! (THE BUCKET THAT SPLIT) AND SPLITBD1 (THE NEWLY ALLOCATED
! BUCKET) WILL BE MODIFIED TO REFLECT THE INDEX BUCKET
! AND ANY NEWLY ALLOCATED INDEX BUCKET. THUS, THIS ROUTINE
! MODIFY THE INPUT ARGS SO AS TO SET UP FOR THE NEXT CALL
! TO ITSELF
!
! 3. ON INPUT TO THIS ROUTINE, THE NEW HIGH-KEY VALUE
! FOR THE BUCKET WHICH SPLIT IS CONTAINED IN THE
! BOTTOM HALF OF THE RST KEY BUFFER.
! HOWEVER, IF THE BUCKET WHICH SPLIT NOW CONTAINS
! ONLY RRV RECORDS, THEN A NEW INDEX RECORD NEED
! NOT BE CREATED. THIS CONDITION IS INDICATED BY
! THE "NOHIKEY" FLAG BEING SET. IF SO, WE ONLY
! NEED TO CHANGE THE OLD INDEX ENTRY TO POINT
! TO THE NEW (I.E., SPLIT) BUCKET.
! THIS ACTION HAS THE IMPORTANT EFFECT OF REMOVING
! A BUCKET WHICH CONTAINS ONLY RRV'S FROM THE VERTICAL
! TREE PATH.
!
! 4. ALL INDEX BUCKETS ARE WRITTEN OUT IN THIS ROUTINE.
GLOBAL ROUTINE INSRTIRECORD ( RECDESC, INDEXBD, ORIGINALBD, SPLITBD1, SPLITBD2 ) =
BEGIN
ARGUMENT (RECDESC,BASEADD);
ARGUMENT (INDEXBD,BASEADD);
ARGUMENT (ORIGINALBD,BASEADD);
ARGUMENT (SPLITBD1,BASEADD);
ARGUMENT (SPLITBD2,BASEADD);
MAP
RECDESC: POINTER,
INDEXBD: POINTER,
ORIGINALBD: POINTER,
SPLITBD1: POINTER,
SPLITBD2: POINTER;
REGISTER
TEMPAC,
PTRAC: POINTER, ! TEMPORARY POINTER
OLDIRECORDPTR: POINTER;
LOCAL
INSERTPTR: POINTER, ! ADDRESS TO INSERT RECORD
OLDIBKTPTR: POINTER, ! PTR TO THE ORIGINAL INDEX BUCKET
NEWHIGHKEYPTR: POINTER, ! PTR TO NEW HIGH-KEY
TOTALSIZE, ! AMOUNT OF SPACE NEEDED
SPLITFLAG, ! ON IF WE NEED TO SPLIT
BUCKETSIZE, ! SIZE IN WORDS OF A BUCKET
MAXOFFSET, ! MAX OFFSET INTO BKT BEFORE WE SPLIT
ROOTSPLITFLAG, ! ON IF WE SPLIT THE ROOT
NOOFIDXRECORDS, ! NUMBER OF INDEX RECORDS TO CREATE
FREESPACE, ! FREE SPACE LEFT IN THIS BUCKT
TOPOFINDEXPTR: POINTER, ! PTR TO TOP OF CURRENT BUCKET
SIZEOFIDXRECORD, ! GUESS
KEYSTRINGPTR: POINTER, ! PTR TO KEY STRING
BUCKETTOINDEX, ! BKT NUMBER TO PUT IN INDEX
KEYSIZEINWORDS,
NEWINDEXBD: FORMATS[ BDSIZE ]; ! BKT DESC FOR NEW INDEX BUCKET
TRACE ('INSRTIRECORD');
CHECKEXACTCOUNT;
%([ ASSUME WE WON'T SPLIT THE INDEX ])%
ROOTSPLITFLAG = FALSE;
SPLITFLAG = FALSE;
NOOFIDXRECORDS = .RECDESC [ RDCOUNT ]; ! GET # OF SPLIT BUCKETS
KEYSIZEINWORDS = .KDB [ KDBKSZW ];
%([ CHECK SOME MORE INPUT VALUES ])%
CHECKINPUT ( RECDESC[RDCOUNT],GTR,ZERO);
CHECKINPUT ( RECDESC[RDCOUNT],LEQ,2);
%([ GET THE ADDRESS OF THE CURRENT INDEX RECORD ])%
OLDIRECORDPTR = .RECDESC [ RDRECPTR ];
%([ GET A POINTER TO THE BOTTOM HALF OF THE KEY-BUFFER (WHICH
CONTAINS THE NEW HIGH-KEY VALUE FOR THE SPLIT BUCKET) ])%
NEWHIGHKEYPTR = .RST [ RSTKEYBUFF ] + ( .FST [ FSTKBFSIZE ] / 2 );
%([ ASSUME THAT WE WON'T NEED ANY FURTHER SPLITS ])%
CLRFLAG ( RECDESC [ RDSTATUS ], RDFLGIDXUPDATE );
%([ COMPUTE SIZE OF AN INDEX RECORD ])%
SIZEOFIDXRECORD = .KEYSIZEINWORDS + IRHDRSIZE;
%([ CALCULATE HOW MUCH SPACE WE NEED AND HOW MUCH WE HAVE ])%
TOTALSIZE = .SIZEOFIDXRECORD * .NOOFIDXRECORDS;
%([ FIND THE LOCATION WHERE WE WILL ATTEMPT TO PLACE
THE NEW INDEX RECORD (JUST BEYOND THE OLD INDEX RECORD) ])%
INSERTPTR = .OLDIRECORDPTR + .SIZEOFIDXRECORD;
%([ IF THERE IS NO HIGH-KEY RECORD IN THE ORIGINAL BUCKET,
JUST CHANGE THE EXISTING INDEX RECORD TO POINT TO THE
NEW BUCKET ])%
IF ( CHKFLAG ( RECDESC [ RDSTATUS ], RDFLGNOHIKEY ) ISON )
THEN
BEGIN
RTRACE (%STRING(' NO HI-KEY FOUND',%CHAR(13),%CHAR(10)));
OLDIRECORDPTR [ IRBUCKET ] = .SPLITBD1 [ BKDBKTNO ];
%([ ADJUST THE AMOUNT OF SPACE WE WILL NEED ])%
DEC ( TOTALSIZE, .SIZEOFIDXRECORD );
%([ INSERT NEW INDEX RECORD BEFORE OLD ONE ])%
DEC ( INSERTPTR, .SIZEOFIDXRECORD );
%([ IF THIS IS A 2-BKT SPLIT (NORMAL CASE), WE CAN EXIT ])%
IF .NOOFIDXRECORDS IS 1
THEN %(JUST RELEASE THE BUCKET)%
BEGIN
CALLPUTBKT ( %(UPDATE)% PCI ( NOHIKEYUPDFLAG ), BPT ( INDEXBD ) );
GOODRETURN ! EXIT OK
END %(OF IF THERE WAS NOT A NEW HIGH KEY RECORD)%
END; %(OF IF NOHIKEY IS SET)%
%([ MORE POINTERS ])%
OLDIBKTPTR = ( TOPOFINDEXPTR = .INDEXBD [ BKDBKTADR ]);
%([ WE NOW NEED TO DETERMINE THE POINT AT WHICH WE
SHOULD CONSIDER THE BUCKET TO BE FULL. IF USER
FILL PERCENTAGES ARE BEING USED, THEN WE USE HIS
FILL OFFSET VALUE; OTHERWISE, WE USE THE END OF THE
BUCKET AS THE LIMITING FACTOR ])%
MAXOFFSET = ( BUCKETSIZE = .KDB [ KDBIBKZ ] ^ B2W );
IF ( CHKFLAG ( RAB [ RABROP ], ROPLOA ) ISON )
THEN %(THE USER WANTS TO DEFINE A "FULL" BUCKET)%
MAXOFFSET = .KDB [ KDBIFLOFFSET ];
LOOKAT (' MAXOFFSET: ', MAXOFFSET );
%([ IS THIS BUCKET FULL? ])%
IF ( .OLDIBKTPTR [ BHNEXTBYTE ] + .TOTALSIZE )
GEQ
.MAXOFFSET
THEN %(WE NEED TO SPLIT)%
BEGIN
SPLITFLAG = TRUE;
RTRACE (%STRING(' SPLITTING THE INDEX...',%CHAR(13),%CHAR(10)));
RECDESC [ RDLENGTH ] = .TOTALSIZE; ! TOTAL SPACE WE NEED
RECDESC [ RDRECPTR ] = .INSERTPTR; ! INSERT NEW REC HERE
IF CALLSPTINDEX ( %(RD)% BPT ( RECDESC ),
%(INDEX)% BPT ( INDEXBD ),
%(NEW)% LCT ( NEWINDEXBD ) ) IS FALSE
THEN
RETURN FALSE;
%([ IF THE ROOT SPLIT, WE MUST REMEMBER IT ])%
IF ( CHKFLAG ( TOPOFINDEXPTR [ BHFLAGS ], BHFLGROOT ) ISON )
THEN
ROOTSPLITFLAG = TRUE;
%([ NOW, IS THE NEW RECORD GOING TO GO INTO THE
NEW BUCKET? ])%
IF .INSERTPTR ISNT ( TEMPAC = .RECDESC [ RDRECPTR ])
THEN %(THE NEW RECORD GOES IN NEW BUCKET)%
BEGIN
INSERTPTR = .TEMPAC;
TOPOFINDEXPTR = .NEWINDEXBD [ BKDBKTADR ]
END;
%([ CHECK THAT THERE IS ENOUGH ROOM TO
WRITE THE RECORDS ])%
FREESPACE = ( .BUCKETSIZE ) - .TOPOFINDEXPTR [ BHNEXTBYTE ];
IF .TOTALSIZE GTR .FREESPACE THEN RMSBUG ( MSGNOSPACE )
END; %(OF RECORD CANT FIT)%
%([ AT THIS POINT, WE CAN MORE THE RECORDS DOWN AND
INSERT THE NEW INDEX RECORDS. WE HAVE THE FOLLOWING:
KEYBUFFER CONTAINS NEW HIGH KEY VALUE
INSERTPTR PTR TO POINT AT WHICH
INSERT IS TO BE DONE
OLDIRECORDPTR PTR TO THE OLD INDEX RECORD WHOSE
KEY VALUE WE MUST CHANGE
TOPOFINDEXPTR PTR TO TOP OF BKT IN WHICH WE WILL
INSERT NEW INDEX RECORD
])%
%([ COMPUTE THE END OF THE BUCKET ADDRESS AND CHECK
TO SEE IF THERE ARE ANY INDEX RECORDS WE MUST MOVE DOWN ])%
RTRACE (%STRING(' MOVING IDX RECS DOWN...',%CHAR(13),%CHAR(10)));
PTRAC = .TOPOFINDEXPTR + .TOPOFINDEXPTR [ BHNEXTBYTE ];
LOOKAT (' PTRAC: ', PTRAC );
IF .PTRAC ISNT .INSERTPTR
THEN
MOVEDOWN ( %(FROM)% .INSERTPTR,
%(TO)% .PTRAC - 1,
%(SIZE)% .TOTALSIZE );
%([ IF THIS IS A 3-BUCKET SPLIT, CREATE AN INDEX RECORD
FOR THE RECORD R-NEW ])%
IF .NOOFIDXRECORDS IS 2
THEN
BEGIN
RTRACE (%STRING(' CREATING IDX REC FOR R-NEW...',%CHAR(13),%CHAR(10)));
KEYSTRINGPTR = .RECDESC [ RDUSERPTR ];
BUCKETTOINDEX = .SPLITBD2 [ BKDBKTNO ];
%([ MAKE THE INDEX RECORD ])%
CALLMAKEIRECORD ( %(BKT)% LCI ( BUCKETTOINDEX ),
%(AT)% LPT ( INSERTPTR ),
%(KEY)% LPT ( KEYSTRINGPTR ) );
%([ BUMP THE INSERTPTR OVER THIS INDEX RECORD ])%
INC ( INSERTPTR, .SIZEOFIDXRECORD );
LOOKAT (' INSERTPTR AFTER CREATING R-NEW IDX REC: ', INSERTPTR )
END; %(OF IF THIS WAS A 3-BKT SPLIT)%
%([ WE MUST NOW CREATE AN INDEX RECORD FOR THE NEW BUCKET
WHICH CONTAINS R-HIGH. THIS INDEX RECORD WILL CONSIST OF
ITS BUCKET AND THE KEY STRING IN THE ORIGINAL INDEX
RECORD. NOTE THAT IN THE UNUSUAL CASE THAT THERE WAS A 3-BKT SPLIT
AND THE "NOHIKEY" FLAG WAS SET, THEN WE DON'T WANT TO
DO ALL THIS (IF THE NOHIKEY FLAG IS SET AT THIS POINT,
IT MUST BE A 3-BKT SPLIT SINCE WE WOULD HAVE EXITED EARLIER
IF THIS HAD BEEN A NORMAL SPLIT) ])%
IF ( CHKFLAG ( RECDESC [ RDSTATUS ], RDFLGNOHIKEY ) IS OFF )
THEN
BEGIN
BUCKETTOINDEX = .SPLITBD1 [ BKDBKTNO ]; ! GET BUCKET NUMBER
KEYSTRINGPTR = .OLDIRECORDPTR + IRHDRSIZE;
CALLMAKEIRECORD ( %(BKT)% LCI ( BUCKETTOINDEX ),
%(AT)% LPT ( INSERTPTR ),
%(KEY)% LPT ( KEYSTRINGPTR ) );
%([ WE HAVE NOW CREATED ALL INDEX RECORDS. WE MUST
RESET THE VALUE OF THE KEY IN THE OLD INDEX RECORD ])%
MOVEWORDS ( %(FROM)% .NEWHIGHKEYPTR,
%(TO)% .OLDIRECORDPTR + IRHDRSIZE,
%(SIZE)% .KEYSIZEINWORDS );
%([ CLEAR THE OLD "HIKEY" FLAG AND SET IT IN THE
NEW INDEX RECORD IF IT IS ALREADY SET IN THE
OLD ONE ])%
INSERTPTR [ IRFLAGS ] = .OLDIRECORDPTR [ IRFLAGS ];
OLDIRECORDPTR [ IRFLAGS ] = DEFIRFLAGS
END; %(OF IF NOHIKEY IS OFF)%
%([ BUMP THE END-OF-BUCKET POINTER IN THE BUCKET HEADER ])%
INC ( TOPOFINDEXPTR [ BHNEXTBYTE ], .TOTALSIZE );
%([ WE MUST NOW CHECK TO SEE IF WE SPLIT THE ROOT. IF SO,
WE MUST ALLCATE A NEW ROOT BUCKET THAT CONTAINS AN INDEX
RECORD FOR EACH OF THE TWO NEW INDEX BUCKETS. NOTE THAT
THE ALLOCATION OF THE NEW ROOT SHOULD BE DONE BEFORE
THE OLD ROOT IS WRITTEN OUT (BELOW). THIS IS SO THAT,
AT WORST, SOME EXTRA INDEX RECORDS WILL EXIST IN THE
OLD ROOT (IF A CRASH OCCURED AFTER THE NEW ROOT
HAS BEEN WRITTEN BUT BEFORE THE OLD ROOT CAN BE
WRITTEN TO THE FILE). IF THE OLD ROOT WERE WRITTEN FIRST,
THE POTENTAIL WOULD EXIST FOR THE LOSS OF 1/2 OF THE DATA
RECORDS IN THE FILE BECAUSE THE OLD ROOT WOULD CONTAIN
ONLY HALF OF ITS FORMER ENTRIES. ALSO, THE ROOT BIT
WOULD BE OFF SO WE COULD NEVER LOCATE THE TRUE INDEX ROOT ])%
IF .ROOTSPLITFLAG ISNT FALSE
THEN %(WE MUST ALLOCATE A NEW ROOT)%
BEGIN
RTRACE (%STRING(' ALLOCATING NEW ROOT...',%CHAR(13),%CHAR(10)));
RETURN CALLMAKROOT ( %(BKT)% BPT ( INDEXBD ),
%(BKT-2)% LCT ( NEWINDEXBD ) )
END; %(OF IF ROOTSPLITFLAG IS ON)%
%([ IF WE SPLIT THE INDEX IN ORDER TO ADD THE NEW INDEX
RECORD, WE MUST WRITE OUT THAT BUCKET AND SET UP THE
NEW HIGH-KEY VALUE IN THE KEY BUFFER ])%
IF .SPLITFLAG
THEN
BEGIN
%([ FIND THE LAST INDEX RECORD IN THE OLD INDEX
BUCKET AND MOVE ITS KEY INTO THE BOTTOM OF THE
USER'S KEY BUFFER. ])%
PTRAC = .RST [ RSTKEYBUFF ] + ( .FST [ FSTKBFSIZE ] / 2 );
NEWHIGHKEYPTR = .OLDIBKTPTR + .OLDIBKTPTR [ BHNEXTBYTE ]
- .KEYSIZEINWORDS;
LOOKAT (' MOVING NEW HIGH-KEY AT: ', NEWHIGHKEYPTR );
MOVEWORDS ( %(FROM)% .NEWHIGHKEYPTR,
%(TO)% .PTRAC,
%(SIZE)% .KEYSIZEINWORDS );
%([ NOW, WRITE THE NEW BUCKET OUT ])%
CALLPUTBKT ( %(UPDATE IT)% PCI ( TRUE ),
%(BUCKET)% LCT ( NEWINDEXBD ) )
END; %(OF IF .SPLITFLAG)%
%([ WE NOW NEED TO WRITE OUT THE INDEX BUCKET INTO WHICH
WE TRIED TO INSERT THE NEW INDEX RECORD ])%
CALLPUTBKT ( %(UPDATE)% PCI ( TRUE ),
%(BKT)% BPT ( INDEXBD ) );
%([ IF WE SPLIT, WE MUST MODIFY THE INPUT ARGS TO
REFLECT WHAT WE'VE DONE SO WE CAN BE CALLED AGAIN
EASILY. NOTE THAT THIS IMPLIES THAT WHEN THE DATA
BUCKET DESCRIPTOR IS PASSED TO THIS ROUTINE, IT
MUST ALSO BE PASSED IN A TEMP BECAUSE IT WILL BE
DESTROYED. ])%
IF .SPLITFLAG IS FALSE
THEN
GOODRETURN; ! NO MORE SPLITS NEEDED
SETFLAG ( RECDESC [ RDSTATUS ], RDFLGIDXUPDATE );
%([ RESET THE NUMBER OF BUCKETS IN THE SPLIT SO WE WON'T
SCREW UP IF WE COME BACK TO THIS ROUTINE AGAIN ])%
RECDESC [ RDCOUNT ] = 1;
MOVEBKTDESC ( %(FROM)% INDEXBD, %(TO)% ORIGINALBD );
%([ MAKE THE NEW BUCKET THE SPLIT BUCKET ])%
MOVEBKTDESC ( %(FROM)% NEWINDEXBD, %(TO)% SPLITBD1 );
GOODRETURN
END; %(OF INSRTIRECORD)%
! FNDDATA
! =======
! ROUTINE TO TRAVERSE THE ENTIRE INDEX STRUCTURE FROM THE
! ROOT BUCKET TO THE DATA LEVEL. THIS ROUTINE SIMPLY
! LOCATES THE ROOT, THEN CALLS FNDREC TO TRAVEL TO THE
! DATA LEVEL. THE INDEX BUCKET WILL BE RELEASED REGARDLESS
! OF WHETHER THERE WAS AN ERROR OR NOT DURING THE INDEX
! SEARCH. IF THIS ROUTINE RETURNS SUCCESS, THEN THE
! DATA BUCKET IS MAPPED AND LOCKED. IF NOT, THEN NO
! BUCKETS ARE MAPPED OR LOCKED.
!
! NOTES:
!
! 1. THE INDEX MUST BE LOCKED BEFORE CALLING THIS ROUTINE.
! INPUT:
! RECDESC RECORD DESCRIPTOR PACKET
! USERPTR ADDRESS OF SEARCH KEY
! USERSIZE SIZE OF SEARCH KEY
!
! DATABD BKT DESCRIPTOR OF DATA LEVEL (RETURNED)
! OUTPUT:
! TRUE: DATA LEVEL REACHED, RECORD POSITION FOUND
! FALSE: ERROR
! TREE ERROR
! DATA BUSY (BUSY FLAG WILL BE SET)
! ROUTINES CALLED:
! GETROOT
! FNDREC
GLOBAL ROUTINE FNDDATA ( RECDESC, DATABD ) =
BEGIN
ARGUMENT (RECDESC,BASEADD);
ARGUMENT (DATABD,BASEADD);
MAP
RECDESC: POINTER,
DATABD: POINTER;
LOCAL
INDEXBD: FORMATS[ BDSIZE ]; ! BKT DESCRIPTOR FOR INDEX
REGISTER
SAVEDSTATUS;
TRACE ('FNDDATA');
%([ FETCH THE ROOT ])%
IF CALLGETROOT ( BPT ( RECDESC ),
LCT ( INDEXBD ) ) IS FALSE
THEN
RETURN FALSE;
%([ START SEARCH AT TOP AND GO TO DATA LEVEL ])%
RECDESC [ RDRECPTR ] = ZERO;
RECDESC [ RDLEVEL ] = DATALEVEL; ! GO TO DATA
RETURN CALLFNDREC ( BPT ( RECDESC ),
LCT ( INDEXBD ),
BPT ( DATABD ) )
%([ RETURN THE RESULT OF THE SEARCH ])%
END; %(OF FNDDATA)%
END
ELUDOM