Enter your search terms Submit search form
	Web pdp-10.trailing-edge.com

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