Google
 

Trailing-Edge - PDP-10 Archives - BB-JF18A-BM - sources/rms/rmsixm.b36
There are 6 other files named rmsixm.b36 in the archive. Click here to see a list.
%TITLE 'I D X 2   -- index file support routines'
!<BLF/REQUIRE 'RMSBLF.REQ'>
MODULE idx2 (IDENT = '2.0'
		) =
BEGIN

GLOBAL BIND
    ix2v = 2^24 + 0^18 + 400;			! Edit date: 22-Apr-83

!+
!
!
!	COPYRIGHT (C) DIGITAL EQUIPMENT CORPORATION 1977, 1986.
!	ALL RIGHTS RESERVED.
!
!	THIS SOFTWARE IS FURNISHED UNDER A LICENSE AND MAY  BE  USED  AND
!	COPIED ONLY IN ACCORDANCE WITH THE TERMS OF SUCH LICENSE AND WITH
!	THE INCLUSION OF THE ABOVE COPYRIGHT NOTICE.   THIS  SOFTWARE  OR
!	ANY  OTHER  COPIES  THEREOF MAY NOT BE PROVIDED OR OTHERWISE MADE
!	AVAILABLE TO ANY OTHER PERSON.  NO TITLE TO AND OWNERSHIP OF  THE
!	SOFTWARE IS HEREBY TRANSFERRED.
!
!	THE INFORMATION IN THIS SOFTWARE IS  SUBJECT  TO  CHANGE  WITHOUT
!	NOTICE  AND  SHOULD  NOT  BE CONSTRUED AS A COMMITMENT BY DIGITAL
!	EQUIPMENT CORPORATION.
!
!	DIGITAL ASSUMES NO RESPONSIBILITY FOR THE USE OR  RELIABILITY  OF
!	ITS SOFTWARE ON EQUIPMENT THAT IS NOT SUPPLIED BY DIGITAL.
!
!
!
!    AUTHOR:	S. BLOUNT
!
!    THIS MODULE CONTAINS ROUTINES WHICH MANIPULATE AND
!    ACCESS THE INDEX STRUCTURE OF AN INDEXED FILE. THE
!    ROUTINES CONTAINED IN THIS MODULE GENERALLY ARE LESS
!    USED THAN THE ONES IN "RMSIDX". THUS, THIS MODULE CAN
!    BE SELECTIVELY LOADED WITH OTHER MODULES WHICH ARE NOT
!    COMMONLY EXECUTED ( E.G., ERROR PROCESSING, DEBUGGING
!    ROUTINES, ETC ).
!
!
!
!    **********	TABLE OF CONTENTS	**************
!
!
!
!
!    ROUTINE			FUNCTION
!    =======			========
!
!    MAKIDX			CREATE AN INDEX STRUCTURE FOR A KEY
!
!    ALCROOT			ALLOCATE A ROOT FOR AN INDEX
!
!    MAKROOT			CREATE NEW ROOT ON ROOT SPLIT
!
!    ADJIPTR			ADJUST THE INDEX POINTER FOR INDEX UPDATE
!
!
!
!    REVISION HISTORY:
!
!    EDIT		DATE		WHO			PURPOSE
!    ====		====		===			=======
!
!    1		29-SEP-76	SB		UPDATE IDB LEVELS ON ROOT SPLIT
!    2		23-FEB-77	SB		SET HIKEY FLAG IN INDEX RECORD
!    3		8-MAR-77	SB		TAKE OUR BUG MSG IN ALCROOT
!
!    *************************************************
!    *						*
!    *		NEW REVISION HISTORY		*
!    *						*
!    *************************************************
!
!    PRODUCT	MODULE	 SPR
!    EDIT	 EDIT	 QAR		DESCRIPTION
!    ======	======	=====		===========
!
!	400	400	xxxxx		Clean up BLISS code (RL, 22-Apr-83)
!
!    ***** END OF REVISION HISTORY *****
!
!-

REQUIRE 'RMSREQ';
%SBTTL 'MAKIDX - initialize index structure'

GLOBAL ROUTINE makidx =
! MAKIDX
! =========
! ROUTINE TO INITIALIZE THE INDEX STRUCTURE FOR A SPECIFIC KEY.
!	THIS ROUTINE PERFORMS THE FOLLOWING FUNCTIONS:
!		1.	ALLOCATE AND FORMAT A ROOT BUCKET
!		2.	UPDATE THE ROOT POINTER IN THE INDEX DESCRIPTOR
!			IN THE FILE PROLOGUE, AND IN THE IN-CORE
!			KEY DESCRIPTOR BLOCK
!		3.	ALLOCATE AND FORMAT A NEW DATA BUCKET AND
!			UPDATE THE POINTER IN THE PROLOGUE TO IT.
!		4.	CREATE A SINGLE INDEX RECORD WHICH CONTAINS
!			THE HIGHEST KEY VALUE POSSIBLE.
! INPUT:
!	<NONE>
!
!	ON INPUT, KDB MUST BE SET UP TO POINT TO THE KEY DESCRIPTOR
!	BLOCK OF THE KEY.
! OUTPUT:
!	TRUE:		OK
!	FALSE:		ERROR
!			<NONE>
! ROUTINES CALLED:
!	ALCBKT
!	ALCROOT
!	DUMPIRECORD
!	DUMP
!	CRASH
    BEGIN

    LOCAL
	databd : BLOCK [bdsize],		! BUCKET DESCRIPTOR FOR DATA BUCKET
	rootbd : BLOCK [bdsize],		! BUCKET DESCRIPTOR FOR ROOT
	dataptr : REF BLOCK,			! PTR TO DATA BUCKET
	rootptr : REF BLOCK,			! PTR TO ROOT BUCKET
	irecordptr : REF BLOCK,			! PTR TO INDEX RECORD
	rootbucket,				! BUCKET FOR INDEX ROOT
	databucket;				! THE BUCKET NUMBER OF THE DATA

!+
!    VALUE OF THE HIGHEST KEY POSSIBLE...SEE NOTE BELOW
!-

    LITERAL
	hikeyvalue = -1;

    TRACE ('MAKIDX');

    !+
    !    CHECK INPUT VALUES...JUST CHECK THE KDB POINTER
    !-

    checkinput (kdb, NEQ, 0);

    !+
    !    ALLOCATE A ROOT BUCKET
    !-

    IF alcroot (seqsetlevel, 			! Level
	    rootbd) EQL false			! Bucket descriptor
    THEN
	RETURN false;

    !+
    !    ALLOCATE A NEW DATA BUCKET
    !-

    IF alcbkt (btypedata, 			! Type
	    bhflgend, 				! End of chain
	    datalevel, 				! Level
	    databd) EQL false			! Bucket descriptor
    THEN
	rmsbug (msgfailure);

    !+
    !    FORM A POINTER TO THIS BUCKET
    !-

    databucket = .databd [bkdbktno];
    dataptr = .databd [bkdbktadr];
    dataptr [bhnextbkt] = .databucket;		! POINT TO ITSELF

    !+
    !    FORM A POINTER TO THE ROOT
    !-

    rootbucket = .rootbd [bkdbktno];		! GET BKT # OF ROOT
    rootptr = .rootbd [bkdbktadr];

    !+
    !    SET UP A PTR TO WHERE THE RECORD IS TO GO
    !-

    irecordptr = .rootptr + bhhdrsize;

    !+
    !    CREATE AN INDEX RECORD
    !-

    irecordptr [irflags] = flghikey;		! SET HIGHEST KEY
    irecordptr [irbucket] = .databucket;
    irecordptr = .irecordptr + 1;
!+
!    NOW, WE MUST CREATE A INDEX RECORD WITH THE HIGHEST
!    POSSIBLE KEY VALUE, WHICH IS -1. NOTE THAT THIS VALUE
!    MAY CAUSE PROBLEMS WHEN COMP KEYS ARE SUPPORTED. THUS,
!    IF AND WHEN THIS IS TRUE, A SPECIAL CHECK MAY HAVE TO
!    BE MADE FOR THESE KEY TYPES. ALSO, THE "FLGHIKEY" CAN
!    ALWAYS BE USED TO DETERMINE IF THIS IS THE SPECIAL
!    TYPE OF INDEX RECORD
!-

    INCR j FROM 1 TO .kdb [kdbkszw] DO
	%(ONCE FOR EACH WORD OF THE KEY)%
	BEGIN
	irecordptr [wholeword] = hikeyvalue;	! STORE THE HIGHEST POSSIBLE KEY
	irecordptr = .irecordptr + 1;
	END;					! Of INCR loop

    !+
    !    RESET THE END-POINTER
    !-

    rootptr [bhnextbyte] = .irecordptr - .rootptr;

    !+
    !    RELEASE BOTH BUCKETS
    !-

    putbkt (%(UPDATE)%true, %(BKT-DESC)%databd);
    putbkt (%(UPDATE)%true, %(BKT-DESC)%rootbd);
    RETURN true
    END;

%(OF MAKIDX)%
%SBTTL 'ALCROOT - allocate a new root'

GLOBAL ROUTINE alcroot (level, rootbd) =
! ALCROOT
! =========
! ROUTINE TO ALLOCATE A NEW ROOT FOR A PARTICULAR INDEX.
!	THIS ROUTINE ALLOCATES A NEW ROOT, FORMATS IT,
!	AND UPDATES THE ROOT BUCKET POINTER IN THE INDEX
!	DESCRIPTOR BLOCK IN THE FILE PROLOGUE. IT ALSO
!	UPDATES THE ROOT BUCKET NUMBER IN THE CURRENT
!	IN-CORE KEY DESCRIPTOR BLOCK (POINTED TO BY KDB).
! INPUT:
!	LEVEL	=	LEVEL # OF NEW ROOT
!	ROOTBD	=	BUCKET DESCRIPTOR OF NEW ROOT (RETURNED)
! OUTPUT:
!	TRUE:	OK
!	FALSE:	ERROR
!		ROOT HAS ALREADY BEEN CREATED
!		NO BUCKETS LEFT IN FILE
! NOTES:
!	1.	THE ROOT IS <NOT> WRITTEN OUT TO THE FILE
!		IN THIS ROUTINE. THE CALLER IS RESPONSIBLE
!		FOR DOING SO.
! ROUTINES CALLED:
!	ALCBKT
!	GETIDB
!	DUMP
    BEGIN

    LOCAL
	idbptr : REF BLOCK,			! PTR TO INDEX DESCRIPTOR
	savestatus,				! USED TO SAVE STATUS
	plogbktdesc : BLOCK [bdsize];		! BKT DESC OF PROLOGUE

    REGISTER
	rootptr : REF BLOCK;

    MAP
	rootbd : REF BLOCK;

    TRACE ('ALCROOT');
!+
!    FIRST, WE MUST FIND THE INDEX DESCRIPTOR ON DISK
!    AND MAKE SURE THAT A ROOT HAS NOT BEEN CREATED
!    SINCE WE OPENED THE FILE.
!-

    IF (idbptr = getidb (plogbktdesc)) EQL false THEN RETURN false;

    !+
    !    IS THERE NOW A ROOT
    !-

    IF .idbptr [idbroot] NEQ 0
    THEN
	%(THERE IS A NEW ROOT)%savestatus = false	! REMEMBER WE DIDNT DO IT
    ELSE
	BEGIN
!+
!    THERE IS NO ROOT FOR THE FILE. WE MUST ALLOCATE
!    A NEW ROOT BUCKET
!-

	IF alcbkt (btypeindex, 			! Type
		bhflgroot + bhflgend, 		! Flags
		.level, 			! Level
		.rootbd) EQL false		! Bucket descriptor
	THEN
	    RETURN false;

	rootptr = .rootbd [bkdbktadr];
	idbptr [idbroot] = (rootptr [bhnextbkt] = .rootbd [bkdbktno]);
	idbptr [idblevels] = seqsetlevel;	! SET LEVEL #
	savestatus = true
	END;%(OF ELSE THERE IS NO ROOT FOR THE FILE)%

    !+
    !    STORE THE NEW ROOT BUCKET # IN THE IDB
    !-

    kdb [kdbroot] = .idbptr [idbroot];
    clrflag (kdb [kdbflags], flgnoindex);

    !+
    !    RETURN THE BUCKET DESCRIPTOR FOR THE FILE PROLOGUE
    !-

    putbkt (%(NO UPDATE)%false, %(DESC)%plogbktdesc);
    RETURN .savestatus
    END;

%(OF ALCROOT)%
%SBTTL 'MAKROOT - make a new root bucket'

GLOBAL ROUTINE makroot (old_root_bd, new_index_bd) =
! MAKROOT
! =======
! ROUTINE TO CREATE A NEW ROOT BUCKET WHEN THE OLD ROOT BUCKET
!	SPLITS DUE TO A RECORD INSERTION.
!	THIS ROUTINE DOES THE FOLLOWING OPERATIONS:
!
!		1.	ALLOCATE NEW BUCKET
!		2.	MOVE ALL DATA FROM OLD ROOT INTO THIS BUCKET
!		3.	CREATE 2 INDEX RECORDS IN THE OLD ROOT
!		4.	WRITE OUT THE NEW BUCKET (WITH DATA IN OLD ROOT)
! INPUT:
!	OLD_ROOT_BD		BKT DESCRIPTOR OF OLD ROOT
!	NEW_INDEX_BD		BKT DESCRIPTOR OF NEW BKT IN THE SPLIT
! OUTPUT:
!	TRUE:	OK
!	FALSE:	ERROR
!		NO MORE BUCKETS
! ROUTINES CALLED:
!	MAKEIRECORD
!	ALCBKT
!	DUMP
!	PUTBKT
!	GETIDB
    BEGIN

    MAP
	old_root_bd : REF BLOCK,
	new_index_bd : REF BLOCK;

    REGISTER
	temp_ptr : REF BLOCK;

    LOCAL
	new_bkt_bd : BLOCK [bdsize],		! New root descriptor
	new_bucket,				! New root bkt #
	bucket_number,				! Temp for a bucket number
	root_level,				! Level of new root
	old_root_ptr : REF BLOCK,		! Some pointers
	new_bkt_ptr : REF BLOCK,		! Same
	index_record_ptr : REF BLOCK,
	size_of_key,				! Size of this key string
	last_record_ptr : REF BLOCK,		! Ptr to last rec in old bucket
	split_bkt_ptr : REF BLOCK,		!
	plog_bd : BLOCK [bdsize],		! Descriptor for prologue
	idb_ptr : REF BLOCK;			! Ptr to index descriptor

    TRACE ('MAKROOT');

    !+
    !    GET SOME POINTERS
    !-

    old_root_ptr = .old_root_bd [bkdbktadr];
    root_level = .old_root_ptr [bhlevel];	! AND LEVEL #

    !+
    !    ALLOCATE A NEW BUCKET FOR THE NEW ROOT
    !-

    IF alcbkt (btypeindex, 			! Type
	    0, 					! Flags
	    .root_level, 			! Level
	    new_bkt_bd) EQL false		! Bucket
    THEN
	RETURN false;				! No

    !+
    !    GET A POINTER TO THE NEW BUCKET
    !-

    new_bkt_ptr = .new_bkt_bd [bkdbktadr];
    new_bucket = .new_bkt_bd [bkdbktno];

    !+
    !    SET UP A POINTER TO WRITE INDEX RECORD
    !-

    index_record_ptr = .old_root_ptr + bhhdrsize;
!+
!    WE WILL NOW MOVE ALL THE DATA IN THE OLD ROOT INTO
!    THE BUCKET WHICH WE JUST ALLOCATED. THEN WE WILL
!    CREATE TWO NEW INDEX ENTRIES IN THE OLD ROOT
!-
    movewords (%(FROM)%.old_root_ptr, %(TO)%.new_bkt_ptr, %(SIZE)%.old_root_ptr [bhnextbyte]);
!+
!    SET THE NEXT-BUCKET FIELDS AND RESET THE FLAG FIELD
!    OF THE OLD ROOT BECAUSE "SPTINDEX" CLEARED THE END
!    FLAG BIT WHEN IT SPLIT THE INDEX BUCKET
!-
    new_bkt_ptr [bhflags] = 0;			! CLEAR OLD ROOT FLAGS
    temp_ptr = .new_index_bd [bkdbktadr];	! PTR TO NEW BKT
    temp_ptr [bhnextbkt] = .new_bucket;
    old_root_ptr [bhnextbkt] = .old_root_bd [bkdbktno];
    old_root_ptr [bhflags] = bhflgroot + bhflgend;
!+
!    NOW, WE MUST FIND THE LAST INDEX RECORD IN THE OLD ROOT.
!    WE CAN DO THIS BECAUSE WE KNOW THE SIZE OF EACH INDEX
!    RECORD, AND WE KNOW WHERE THE BUCKET ENDS.
!-
    size_of_key = .kdb [kdbkszw];		! SIZE OF KEY PORTION OF INDEX RECORD
    last_record_ptr = .new_bkt_ptr + .new_bkt_ptr [bhnextbyte] - .size_of_key;
!+
!    LAST_RECORD_PTR NOW POINTS TO THE LAST KEY (NOT THE INDEX
!    RECORD, BUT THE ACTUAL KEY STRING) IN THE OLD ROOT BUCKET
!-
    lookat ('	LAST-KEY-PTR: ', last_record_ptr);
    bucket_number = .new_bkt_bd [bkdbktno];

    !+
    !    CREATE AN INDEX RECORD WHICH DESCRIBES WHAT USED TO BE THE OLD ROOT
    !-

    makeirecord (.bucket_number, 		! BKT
	.index_record_ptr, 			! PLACE
	.last_record_ptr);			! KEY

    !+
    !    SET UP TO WRITE NEXT INDEX RECORD
    !-

    index_record_ptr = 				! Bump pointer
    .index_record_ptr + .size_of_key + irhdrsize;
    lookat ('	NEXT IDX REC AT: ', index_record_ptr);
    split_bkt_ptr = .new_index_bd [bkdbktadr];
    last_record_ptr = .split_bkt_ptr + .split_bkt_ptr [bhnextbyte] - .size_of_key;
    lookat ('	ADR OF LAST KEY IN NEW BKT: ', last_record_ptr);
    bucket_number = .new_index_bd [bkdbktno];

    !+
    !    CREATE THE SECOND INDEX RECORD
    !-

    makeirecord (%(BKT)%.bucket_number, %(PLACE)%.index_record_ptr, %(KEY)%.last_record_ptr);

    !+
    !    RESET THE BUCKET HEADER DATA IN THE NEW ROOT
    !-

    old_root_ptr [bhnextbyte] = bhhdrsize + (2*(irhdrsize + .size_of_key));

    !+
    !    INCREMENT THE LEVEL NUMBER OF THE OLD ROOT
    !-

    old_root_ptr [bhlevel] = .old_root_ptr [bhlevel] + 1;
!+
!    UPDATE THE NUMBER OF LEVELS IN THIS INDEX IN THE
!    FILE PROLOGUE
!-

    IF (idb_ptr = getidb (plog_bd)) NEQ false
    THEN
	%(WE SUCCEEDED)%
	BEGIN
	idb_ptr [idblevels] = .old_root_ptr [bhlevel];
	putbkt (%(NO UPDATE)%false, %(BKT)%plog_bd)
	END;%(OF IF GETIDB WAS OK)%

!+
!    WE MUST NOW WRITE OUT ALL THE BUCKETS WHICH WERE
!    INVOLVED IN THIS OPERATION. WE HAVE THE FOLLOWING:
!
!    OLD_ROOT_BD	BKT CONTAINING NEW ROOT
!    NEWBKTTBD	BKT WHICH NOW CONTAINS TOP HALF
!    OF OLD ROOT (I.E., 1ST BUCKET IN
!    THE LEVEL UNDER THE ROOT)
!    NEW_INDEX_BD	BKT WHICH NOW CONTAINS BOTTOM HALF
!    OF OLD ROOT.
!
!    WE MUST WRITE THESE NON-ROOT BUCKETS OUT FIRST TO AVOID
!    DATA INTEGRITY PROBLEMS.
!-
    putbkt (%(UPDATE)%true, %(SPLIT-BKT)%.new_index_bd);
    putbkt (%(UPDATE)%true, %(NEW ROOT)%new_bkt_bd);
    putbkt (%(UPDATE)%true, %(ROOT)%.old_root_bd);
    RETURN true
    END;

%(OF MAKROOT)%
%SBTTL 'ADJIPTR - Adjust index record pointer'

GLOBAL ROUTINE adjiptr (recdesc, indexbd) =
! ADJIPTR		ADJUST INDEX POINTER
! =======
! ROUTINE TO ADJUST THE POINTER TO THE CURRENT INDEX RECORD SO AS
!	TO CORRECTLY REFLECT THE PLACE WHERE A NEW INDEX RECORD SHOULD
!	BE INSERTED. THIS ROUTINE IS CALLED ONLY WHEN THE KEY OF THE
!	NEW HIGH RECORD IN A SPLIT BUCKET IS GREATER THAN THE KEY OF
!	THE INDEX RECORD DENOTED BY THE PATH ARRAY. THIS IS CAUSED BY
!	THE INSERTION OF A DUP WHICH MUST BE PLACED IN A DIFFERENT BUCKET
!	FROM THE INITIAL SEARCH BUCKET. (SEE THE NOTES IN "IDXUPDATE" FOR
!	A FULL DESCRIPTION OF WHAT'S HAPPENING).
!
! INPUT:
!	RECDESC		RECORD DESCRIPTOR PACKET
!		RECPTR		ADDRESS OF CURRENT INDEX RECORD
!		USERPTR		ADDRESS OF USER SEARCH KEY (NEW HI-KEY VALUE)
!
!	INDEXBD		BUCKET DESCRIPTOR OF CURRENT BUCKET
!
! OUTPUT:
!	<TRUE ALWAYS>
!
! INPUT ARGS MODIFIED:
!
!	RECORD DESCRIPTOR:
!		RECPTR		ADDRESS OF NEW CURRENT INDEX RECORD
!
!	BUCKET DESCRIPTOR:	NEW BUCKET DESCRIPTOR
    BEGIN

    MAP
	recdesc : REF BLOCK,
	indexbd : REF BLOCK;

    LITERAL
	nolock = false;				! Don't lock next bucket

    LOCAL
	nextbd : BLOCK [bdsize],		! Use for next bucket
	savedstatus;				! Temp storage

    TRACE ('ADJIPTR');
!+
!    WE NOW WANT TO REPOSITION OURSELVES ACCORDING TO THE HIGHEST
!    KEY IN THE OLD BUCKET, INSTEAD OF THE KEY OF THE NEW RECORD.
!    MOST LIKELY, THIS CALL WILL MOVE US DOWN ONE INDEX RECORD
!-

    IF sindexbkt (.recdesc, 			! Record
	    .indexbd) NEQ false			! Bucket

	!+
	!    IF WE SUCCEEDED, THEN WE CAN EXIT
	!-

    THEN
	RETURN true;

!+
!    WE DIDN'T FIND IT. THIS MUST BE THE LAST INDEX RECORD
!    IN THE BUCKET
!-
    rtrace ('	*****COULDNT ADJ I PTR');
    savedstatus = gtnbkt (%(THIS BKT)%.indexbd, %(NEXT BKT)%nextbd, %(NO LOCK)%nolock);

    !+
    !    RELEASE THE OLD ONE, REGARDLESS OF IF WE GOT THE NEXT ONE
    !-

    putbkt (%(NO UPDATE)%false, %(BKT)%.indexbd);

    !+
    !    START SEARCH AT TOP OF NEXT BUCKET
    !-

    recdesc [rdrecptr] = 0;

    IF (.savedstatus EQL false) OR (sindexbkt (.recdesc, nextbd) EQL false)
    THEN 					! If either of these failed, we are really screwed up
	rmsbug (msgfailure);

    !+
    !    RESET BUCKET DESCRIPTORS
    !-

    movebktdesc (%(FROM)%nextbd, %(TO)%indexbd);
    RETURN true
    END;

END

ELUDOM