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