Macintosh-SW/sys7.1-doc-wip
1
0
Fork 0
mirror of https://github.com/elliotnunn/sys7.1-doc-wip.git synced 2024-06-11 23:29:30 +00:00
Code Issues Projects Releases Wiki Activity
master
sys7.1-doc-wip/OS/HFS/BTMAINT2.a
Horst Beepmanh 33cd9271f4 SuperMarioProj.1994-02-09
2019-07-27 22:37:48 +08:00

1172 lines
33 KiB
Plaintext
Raw Permalink Blame History

;
; File: BTMAINT2.a
;
; Contains: These routines provide single-node BTree maintenance functions.
;
; Written by: Bill Bruffey
;
; Copyright: © 1984-1991 by Apple Computer, Inc., all rights reserved.
;
; Change History (most recent first):
;
; <4> 9/10/91 JSM Cleanup header.
; <3> 9/21/90 BG Removed <2>. 040s are behaving more reliably now.
; <2> 6/20/90 CCH Added some temporary NOPs to prevent pipeline problems in
; 68040's.
; <1.3> 5/4/89 KST Fixed a bug in GetMaxkey.
; 5/4/89 KSCT Fixed a bug in GetmaxKey, should add 2, not 1
; <1.2> 3/2/89 DNF removed references to forROM; HFS now builds identically for ram
; or rom
; <1.1> 11/10/88 CCH Fixed Header.
; <1.0> 11/9/88 CCH Adding to EASE.
; <•1.1> 9/23/88 CCH Got rid of inc.sum.d and empty nFiles
; <1.0> 2/11/88 BBM Adding file for the first time into EASE…
; 10/25/85 BB Added vectors for ROM versions.
; 10/22/85 BB Moved LocBTCB from BTIntf to BTMaint2.
; 10/10/85 BB Added use of new MOVEQ equates for GetBlock and RelBlock. Added
; GetMaxKey subroutine and a call to it in BuildIRec. Did some
; minor code clean up.
; 9/26/85 BB Modified GetNode to release the cache block after detecting a
; bad BTree node.
; 9/24/85 PWD Changed '.Word $F042' to _TFSDSErr macro.
; 9/23/85 BB Modified RelNode to handle a null node pointer and to call
; ChkNode.
; 9/23/85 BB Added ClrNode and a call to it in InitNode.
; 9/6/85 BB Fixed minor bugs in GetNodeSize and GetOffA.
; 8/29/85 BB Changed ChkNode to use a more efficient method for checking
; record offsets.
; 8/22/85 BB Added GetNode,RelNode, and ChkNode.
; 8/8/85 BB Modified GetOffset and InitNode for new node format.
; 7/31/85 BB Fixed bug in LocRec which was causing the "write" problem.
; 7/17/85 BB Added GetNodeSiz. Modified GetRecA to also return record size.
; 7/8/85 BB Modified GetLtSib/GetRtSib to use links to locate sibling nodes
; instead of using the TPT.
; 6/10/85 BB Cleaned up some.
; 3/15/85 BB Modified to use A6 stack.
; 3/11/85 BB Added extend BTree file stuff.
; 2/25/85 BB Modified InsertRec to return node number and record index of new
; record.
; 2/18/85 BB Modified LocRec to support variable length keys in leaf nodes.
; 2/13/85 BB Removed default KeyCompare routine
; 1/17/85 BB Removed use of BTree Global area (BTG).
; 1/5/85 BB Added KeyCompare routine.
; 1/5/85 BB Changed CopyRec to LocRec to support return of key and data
; record pointers instead of copying that data.
; 1/5/85 BB Modified SearchNode to use external key compare routine.
; 10/1/84 BB Split off from BTmaint.
;
;__________________________________________________________________________________
;
; External
; Routines: BuildIRec - Builds an index record for a specified target node.
; ChkNode - Checks the validity of a node.
; ClrNode - Clears a node (to zero).
; DeleteRec - Deletes a record from a BTree node.
; GetMaxKey - Gets max key size rounded to word boundry.
; GetNode - Gets a BTree node from disk.
; GetNodeSiz - Gets the size of the data currently contained in a
; node (record data + offset overhead).
; GetLtSib - Gets left sibling node for a given BTree node.
; GetRtSib - Gets right sibling node for a given BTree node.
; GetOffset - Gets the record offset and the pointer to the offset
; word for a given record index.
; GetRecA - Gets the address of the record for a given record
; index.
; InitNode - Gets a cache buffer for a new node and initializes it to
; an empty state.
; InsertRec - Inserts a record into a BTree node.
; LocBTCB - Locates the BTCB for a BTree file.
; LocRec - Locates the key and data records for a specified
; BTree record.
; LocTPR - Locates the Tree Path Record (TPR) for a given tree
; level.
; MovOffLt - Move offsets left within a single node.
; MovOffRt - Move offsets right within a single node.
; MovRecLt - Move records left within a single node.
; MovRecRt - Move records right within a single node.
; RelNode - Releases the use of a node.
; SearchNode - Searches a BTree node for a specified key.
; UpdDRec - Updates the data portion of a BTree record.
; UpdIKey - Updates the key portion of an index record.
;
; Internal
; Subroutines: None.
;
;__________________________________________________________________________________
BLANKS ON
STRING ASIS
PRINT OFF
LOAD 'StandardEqu.d'
PRINT ON
PRINT NOGEN
BTMaint2 PROC EXPORT
EXPORT BuildIRec,ChkNode,ClrNode,DeleteRec
EXPORT GetMaxKey,GetNode,GetNodeSiz,GetLtSib,GetRtSib,GetOffset,GetRecA
EXPORT InitNode,InsertRec,LocBTCB,LocRec,LocTPR
EXPORT MovOffLt,MovOffRt,MovRecLt,MovRecRt
EXPORT RelNode,SearchNode,UpdDRec,UpdIKey
EXPORT vGetNode,vRelNode
IMPORT GetBlock,RelBlock
;__________________________________________________________________________________
;
; Routine: BuildIRec
;
; Function: Builds an index record for a specified target node. The
; record is built in the BTree buffer.
;
; Input: A1.L - ptr(target node buffer)
; D0.W - target node number
; A4.L - pointer to BTCB
;
; Output: A1.L - ptr(new index record) in BTree buffer
;
; Called by: BTInsert
;__________________________________________________________________________________
BuildIRec
MOVE.L D2,-(SP) ; save regs
MOVE.L D0,D2 ; save node number
CLR.W D0 ; locate 1st record
BSR GetRecA ; ...in node
MOVEA.L BTCVarPtr(A4),A1 ; locate record buffer
LEA BTVRecord(A1),A1 ;
JSR UpdIKey ; move in the key
BSR GetMaxKey ; node # offset = max key size <10Oct85>
MOVE.L D2,0(A1,D0.W) ; move in the node number <10Oct85>
MOVE.L (SP)+,D2 ; restore regs
RTS ; exit BuildIRec
;__________________________________________________________________________________
;
; Routine: ChkNode
;
; Function: Checks the validity of a node.
;
; Input: A1.L - pointer to node buffer
; A4.L - pointer to BTCB
;
; Output D0.W - result code
; 0 - ok
; BTBadNode - bad node structure detected
;
; Called by: GetNode
;__________________________________________________________________________________
ChkNode
MOVEM.L D1-D2/A0-A2,-(SP) ; save registers
MOVE.W BTCRefNum(A4),D1 ; locate the FCB
MOVEA.L FCBSPtr,A2 ;
;
; check out the links
;
MOVE.L FCBPLen(A2,D1.W),D0 ; PEOF / node size
DIVU BTCNodeSize(A4),D0 ; = end node # + 1
MOVEQ #0,D1 ;
MOVE.W D0,D1 ; D1 = end node # + 1
CMP.L NDFlink(A1),D1 ; forward link within range?
BLS.S CNBadNode ; no, error ->
CMP.L NDBlink(A1),D1 ; backward link within range?
BLS.S CNBadNode ; no, error ->
;
; check node type
; note: valid node types are $FF (leaf node) to $02 (map node)
;
MOVE.B NDType(A1),D0 ; node type + 1
ADDQ.B #1,D0 ;
CMP.B #NDMapNode+1,D0 ; (node type +1) > (max type +1) ?
BHI.S CNBadNode ; yes, error ->
;
; check node height
;
MOVE.B NDNHeight(A1),D0 ; node height > tree depth?
CMP.B BTCDepth+1(A4),D0 ;
BHI.S CNBadNode ; yes, error ->
;
; check number of records
;
CNChkNRecs
MOVEQ #0,D1 ; D1 = node size
MOVE.W BTCNodeSize(A4),D1 ;
MOVEQ #-lenND,D0 ; max number of records
ADD.L D1,D0 ; = (node size - length of ND)
DIVU #6,D0 ; / (min record size + offset word)
CMP.W NDNRecs(A1),D0 ; record count within range?
BLO.S CNBadNode ; no, error ->
;
; check record offsets
;
CNChkOff
MOVE.W NDNRecs(A1),D1 ; loop index = # records
MOVE.W D1,D0 ; locate free space offset <29Aug85>
BSR GetOffset ;
MOVEQ #2,D2 ; prime previous offset to <29Aug85>
ADD.L A0,D2 ; ptr(free space offset) + 2 <29Aug85>
SUB.L A1,D2 ; - ptr(node) <29Aug85>
@1 MOVE.W (A0)+,D0 ; get next offset <29Aug85>
BTST #0,D0 ; odd offset?
BNE.S CNBadNode ; yes, error ->
CMPI.W #LenND,D0 ; offset >= min ?
BLO.S CNBadNode ; no, error ->
CMP.W D2,D0 ; offset < previous ?
BHS.S CNBadNode ; no, error ->
MOVE.W D0,D2 ; previous offset = current offset
DBRA D1,@1 ; check next one ->
BRA.S CNExit ; all done ->
;
; clean up and exit
;
CNBadNode
MOVEQ #BTBadNode,D0 ; result = 'bad node' <14Oct85>
BRA.S CNExit1 ; exit ->
CNExit
CLR.W D0 ; result = 'ok'
CNExit1
MOVEM.L (SP)+,D1-D2/A0-A2 ; restore registers
TST.W D0 ; set up condition codes
RTS ; exit ChkNode
;__________________________________________________________________________________
;
; Routine: ClrNode
;
; Function: Clears a node to all zeroes.
;
; Input: A0.L - pointer to node buffer
; A4.L - pointer to BTCB
;
; Output none
;
; Called by: BTDelete
;__________________________________________________________________________________
ClrNode
MOVEM.L D0-D1/A0,-(SP) ; save registers <23Sep85>
MOVEQ #3,D1 ; loop index <10Oct85>
ADD.W BTCNodeSize(A4),D1 ; = node size <10Oct85>
LSR.W #2,D1 ; (in long words) <23Sep85>
SUBQ.W #1,D1 ; - 1 <23Sep85>
MOVEQ #0,D0 ; clear the node buffer <23Sep85>
@1 MOVE.L D0,(A0)+ ; <23Sep85>
DBRA D1,@1 ; <23Sep85>
MOVEM.L (SP)+,D0-D1/A0 ; restore registers <23Sep85>
RTS ; exit ClrNode <23Sep85>
;__________________________________________________________________________________
;
; Routine: DeleteRec
;
; Function: Deletes a record from a BTree node.
;
; Input: A1.L - ptr(node buffer)
; D1.W - index of record to be deleted
; A4.L - pointer to BTCB
;
; Output: none
;
; Called by: BTDelete,RotRecLt
;__________________________________________________________________________________
DeleteRec
MOVEM.L D2-D6/A2-A5,-(SP) ; save regs
;
; set up some common stuff
;
MOVE.W D1,D5 ; save delete index
MOVE.W D1,D0 ; get delete offset
JSR GetOffset ;
MOVE.L A0,D6 ; ...D6 = ptr(delete offset)
MOVE.W D0,D4 ; ...D4 = delete offset
LEA -2(A0),A3 ; A3 = ptr(next offset)
MOVE.W (A3),D3 ; D3 = next offset
MOVE.W NDNRecs(A1),D0 ; get last offset
JSR GetOffSet ;
MOVE.L A0,A2 ; ...A2 = ptr(last offset)
MOVE.W D0,D2 ; ...D2 = last offset
;
; Compress remaining records
;
MOVE.L A1,A5 ; save ptr(node buffer)
LEA 0(A5,D3.W),A0 ; source = ptr(next record)
LEA 0(A5,D4.W),A1 ; dest = ptr(delete record)
MOVE.W D2,D0 ; count = last offset
SUB.W D3,D0 ; - next offset
JSR MovRecLt ; move the records
SUB.W #1,NDNRecs(A5) ; decrement number of keys
;
; Adjust the offsets
;
MOVE.L A3,A0 ; source = ptr(next offset)
MOVE.L D6,A1 ; dest = ptr(delete offset)
MOVE.W NDNRecs(A5),D0 ; count = last index
SUB.W D5,D0 ; - delete index
MOVE.W D4,D1 ; delta = delete offset
SUB.W D3,D1 ; - next offset
JSR MovOffRt ; adjust the offsets
DRExit
MOVEM.L (SP)+,D2-D6/A2-A5 ; restore regs
RTS ; return
;__________________________________________________________________________________
;
; Routines: GetLtSib (Get Left Sibling)
; GetRtSib (Get Right Sibling)
;
; Function: Gets the left or right sibling node for a given BTree node. The
; sibling nodes are located using the forward/backward node links.
;
; Input: A0.L - pointer to node buffer containing subject node
; A4.L - pointer to BTCB
;
; Output: A1.L - pointer to node buffer containing sibling node
; D1.L - node number of sibling node
; 0 - no sibling
; D0.W - result code
; 0 - ok
; -n - IO error
;__________________________________________________________________________________
GetLtSib
MOVE.L (SP)+,-(A6) ; save return address on A6 stack
MOVEM.L D2-D3,-(A6) ; save registers
CLR.B D3 ; indicate GetLtSib
BRA.S GSRtSib1 ; use common code
GetRtSib
MOVE.L (SP)+,-(A6) ; save return address on A6 stack
MOVEM.L D2-D3,-(A6) ; save registers
MOVEQ #1,D3 ; indicate GetRtSib
GSRtSib1
TST.B D3 ; getting left sibling ?
BNE.S @2 ; no ->
MOVE.L NDBlink(A0),D2 ; left sibling node number
BRA.S @3 ; ->
@2 MOVE.L NDFlink(A0),D2 ; right sibling node number
@3 BNE.S @5 ; we have the sibling ->
@4 CLR.L D1 ; indicate no sibling
BRA.S GSExit ; exit
@5 MOVEQ #0,D1 ; no GetBlock options <10Oct85>
BSR.S GetNode ; get node from disk
BNE.S GSExit1 ; error ->
MOVE.L D2,D1 ; return the node number
MOVE.L A0,A1 ; ...and buffer address
GSExit
CLR.W D0 ; indicate no error
GSExit1
MOVEM.L (A6)+,D2-D3 ; restore registers
MOVE.L (A6)+,-(SP) ; put return address back on stack
TST.W D0 ; set up condition codes
RTS ; exit GetLtSib/GetRtSib
;__________________________________________________________________________________
;
; Routine: GetMaxKey
;
; Function: Gets maximum key size rounded to word boundry.
;
; Input: A4.L - pointer to BTCB
;
; Output D0.W - maximum key length
;
; Called by: BTInsert,BTDelete,BTGetRecord,BTSearch
;__________________________________________________________________________________
GetMaxKey
MOVEQ #2,D0 ; key length = 1 <10Oct85>
; 2, include length byte <5/4/89>
ADD.W BTCKeyLen(A4),D0 ; + max key length <10Oct85>
LSR.W #1,D0 ; rounded down <10Oct85>
LSL.W #1,D0 ; <10Oct85>
RTS ; exit GetMaxKey <10Oct85>
;__________________________________________________________________________________
;
; Routine: GetNode
;
; Function: Gets an existing BTree node from disk and verifies it.
; Note: this is a temporary interface, it will change for the new
; cache.
;
; Input: D1.B - GetBlock option flags
; D2.L - node number of desired node
; A4.L - pointer to BTCB
;
; Output D0.W - result code
; 0 = ok
; -n = error
; A0.L - pointer to buffer containing node
;
; Called by: BTInsert,BTDelete,BTGetRecord,BTSearch
;__________________________________________________________________________________
GetNode
MOVE.L jGetNode,-(SP) ; jumptable entry for vGetNode <25Oct85>
RTS ; go there <25Oct85>
vGetNode ; 'vectored' GetNode routine <25Oct85>
MOVE.L (SP)+,-(A6) ; save return address on A6 stack
MOVEM.L D1/A1,-(A6) ; save registers
MOVE.W BTCRefNum(A4),D0 ; file refnum
MOVEA.L BTCCQptr(A4),A1 ; ptr to cache queue
JSR GetBlock ; get the block
BNE.S GNExit ; didn't get it ->
MOVEA.L A0,A1 ; verify the node
BSR ChkNode ;
BEQ.S GNExit ; its ok -> <26Sep85>
MOVE.W D0,-(A6) ; save result code <26Sep85>
MOVEQ #kRBTrash,D1 ; set trash option <10Oct85> <26Sep85>
MOVEA.L BTCCQptr(A4),A1 ; ptr to cache queue <26Sep85>
JSR RelBlock ; release it <26Sep85>
MOVE.W (A6)+,D0 ; restore result code <26Sep85>
GNExit
MOVEM.L (A6)+,D1/A1 ; restore registers
MOVE.L (A6)+,-(SP) ; put return address back on stack
TST.W D0 ; set up condition codes
RTS ; exit GetNode
;__________________________________________________________________________________
;
; Routine: GetNodeSiz (Get Node Size)
;
; Function: Gets the size of the data currently contained in a node
; (record data + offset overhead).
;
; Input: A1.L - pointer to node buffer
; A4.L - pointer to BTCB
;
; Output: D0.W - size of node data
;__________________________________________________________________________________
GetNodeSiz
MOVE.L D1,-(SP) ; save registers
MOVE.W NDNRecs(A1),D1 ; number of records in node
MOVE.W D1,D0 ; record data size
JSR GetOffset ; = free space offset
SUBI.W #lenND,D0 ; - length of ND <06Sep85>
LSL.W #1,D1 ; NRecs X 2 = overhead for offsets
ADD.W D1,D0 ; rec data size + offsets = node data size
MOVE.L (SP)+,D1 ; restore registers
RTS ; exit GetNodeSiz
;__________________________________________________________________________________
;
; Routine: GetOffset (Get Offset)
;
; Function: Gets the record offset and the pointer to the offset word
; for a given record index.
;
; Input: A1.L - pointer to node buffer
; D0.W - record index
; A4.L - pointer to BTCB
;
; Output: D0.W - record offset
; A0.L - address of offset word
;__________________________________________________________________________________
GetOffset
BSR.S GetOffA ; get ptr(offset) first
MOVE.W (A0),D0 ; get the offset
RTS ; return
;
; GetOffA (Get Offset Address) subroutine
;
GetOffA
SUBA.L A0,A0 ; position to offset base + 2 <06Sep85>
MOVE.W BTCNodeSize(A4),A0 ; <06Sep85>
ADDA.L A1,A0 ; <06Sep85>
LSL.W #1,D0 ; index * 2 (bytes)
NEG.W D0 ; negative byte index
LEA -2(A0,D0.W),A0 ; ptr(offset) = (base - 2) + byte index
RTS ; return
;__________________________________________________________________________________
;
; Routine: GetRecA (Get Record Address)
;
; Function: Gets the address and size of a BTree record given the record index.
;
; Input: A1.L - ptr(node buffer)
; D0.W - record index
; A4.L - pointer to BTCB
;
; Output: A0.L - record address
; D0.W - size of record
;__________________________________________________________________________________
GetRecA
MOVEM.L D1-D2,-(SP) ; save registers
MOVE.W D0,D1 ; D1 = record index
BSR.S GetOffSet ; get offset of target record
MOVE.W D0,D2 ; D2 = target offset
MOVE.W D1,D0 ; get offset to next record
ADDQ.W #1,D0 ;
BSR.S GetOffSet ;
SUB.W D2,D0 ; size = next offset - target offset
LEA 0(A1,D2.W),A0 ; ptr(record) = base + offset
MOVEM.L (SP)+,D1-D2 ; restore registers
RTS ; return
;__________________________________________________________________________________
;
; Routine: InitNode
;
; Function: Gets a cache buffer for a new node and initializes it to
; an empty state.
;
; Input: D1.L - node number of new node
; A4.L - pointer to BTCB
;
; Output D0.W - result code
; A0.L - ptr(cache buffer containing node)
;
; Called by: BTInsert
;__________________________________________________________________________________
InitNode
MOVE.L (SP)+,-(A6) ; save return address on A6 stack
MOVEM.L D1-D2/A1,-(A6) ; save registers
;
; get cache buffer for new node
;
@1 MOVE.L D1,D2 ; node number
MOVE.W BTCRefNum(A4),D0 ; file refnum
MOVEQ #kGBnoread,D1 ; no-read option <10Oct85>
MOVEA.L BTCCQptr(A4),A1 ; cache queue ptr
JSR GetBlock ; get cache buffer
BNE.S INExit1 ; error ->
;
; initialize the node
;
BSR ClrNode ; clear the node first <23Sep85>
MOVE.W BTCNodeSize(A4),D2 ; D2 = node size
MOVE.W #lenND,-2(A0,D2.W) ; set free space offset
INExit
CLR.W D0 ; result = ok
INExit1
MOVEM.L (A6)+,D1-D2/A1 ; restore registers
MOVE.L (A6)+,-(SP) ; put return address back on stack
TST.W D0 ; set condition codes
RTS ; exit InitNode
;__________________________________________________________________________________
;
; Routine: InsertRec
;
; Function: Inserts a record into a BTree node.
;
; Input: A0.L - pointer to record
; A1.L - ptr(node buffer)
; D0.W - size of record
; D1.W - index of insert point
;
; Output: D0.W - result code
; 0 = ok
; -1 = won't fit
; A1.L - ptr(node buffer) containing new record
; D1.W - index of new record
;
; Called by: BTInsert,RotateLt,RotRecLt
;__________________________________________________________________________________
InsertRec
MOVEM.L D1-D7/A1-A5,-(SP) ; save regs
;
; set up some common stuff
;
MOVE.W D0,D7 ; save size of record
MOVE.W D1,D6 ; save insert index
MOVE.L A0,D5 ; save ptr to record
MOVE.W D1,D0 ; insert index
JSR GetOffset ;
MOVE.W D0,D4 ; D4 = insert offset
MOVE.W NDNRecs(A1),D0 ; number of keys = last index
JSR GetOffSet ;
MOVE.L A0,A3 ; A3 = ptr(last offset)
MOVE.W D0,D3 ; D3 = last offset
;
; see if new record will fit
;
MOVE.L A3,D1 ; ptr(last offset)
CLR.L D0 ;
MOVE.W D3,D0 ; - (last offset + node base)
ADD.L A1,D0 ;
SUB.L D0,D1 ; = avail space
MOVEQ #2,D0 ; 2 + record size
ADD.W D7,D0 ; = required size
CMP.W D0,D1 ; enough space ?
BGE.S IRInsert ; yes ->
MOVEQ #-1,D0 ; indicate "won't fit"
BRA.S IRExit ; exit
;
; make hole for new record
;
IRInsert
MOVE.L A1,A5 ; A5 = ptr(node buffer)
LEA 0(A5,D4.W),A0 ; source = ptr(insert record)
LEA 0(A0,D7.W),A1 ; dest = source + size
MOVE.W D3,D0 ; last offset
SUB.W D4,D0 ; - insert offset = count
JSR MovRecRt ; make hole for new record
;
; adjust offsets for moved records
;
MOVE.L A3,A0 ; source ptr = ptr to last offset
LEA -2(A0),A1 ; dest ptr = source ptr - 2
MOVE.W NDNRecs(A5),D0 ; offset count =
SUB.W D6,D0 ; last index - insert index
MOVE.W D7,D1 ; delta = record size
JSR MovOffLt ; adjust offsets left
;
; move in the new record
;
MOVE.L D5,A0 ; source = ptr(record)
LEA 0(A5,D4.W),A1 ; dest = ptr(insert record)
MOVE.W D7,D0 ; count = record size
JSR MovRecLt ; move record in
ADDQ.W #1,NDNRecs(A5) ; increment key count
CLR.W D0 ; result = ok
IRExit
MOVEM.L (SP)+,D1-D7/A1-A5 ; restore regs
TST.W D0 ; set condition codes
RTS ; exit InsertRec
;__________________________________________________________________________________
;
; Routine: LocBTCB (Locate BTree Control Block)
;
; Function: Locates the BTCB for a BTree file given the refnum.
;
; Input: D0.W - file refnum
;
; Output: A4.L - pointer to BTCB
;__________________________________________________________________________________
LocBTCB
;
; locate BTCB for the file
;
MOVEA.L FCBSPtr,A4 ; start of FCBS
MOVEA.L FCBBTCBptr(A4,D0.W),A4 ; ptr(BTCB)
RTS ; exit LocBTCB
;__________________________________________________________________________________
;
; Routine: LocRec (Locate Record))
;
; Function: Locates the key and data record for a specified BTree record.
;
; Input: A1.L - ptr(node buffer)
; D1.W - record index
; A4.L - pointer to BTCB
;
; Output:
; A0.L - ptr(key)
; A1.L - ptr(data record)
; D1.W - size of record
;__________________________________________________________________________________
LocRec
MOVEM.L D0/D2-D3,-(SP) ; save registers
MOVE.W D1,D3 ; D3 = record index
MOVE.W D3,D0 ; locate
JSR GetRecA ; ...the record
MOVE.L A0,D2 ; D2 = ptr(record)
MOVE.W D3,D0 ; locate
ADDQ #1,D0 ;
JSR GetRecA ; ...the next record
MOVE.L A0,D1 ; D1 = ptr(next record)
MOVEA.L D2,A0 ; ptr(key) = ptr(record)
MOVEQ #0,D0 ; get key length
MOVE.B (A0),D0 ;
ADDQ.L #2,D0 ; include length byte
LSR.L #1,D0 ;
LSL.L #1,D0 ; ...and adjust to word boundry
SUB.L D2,D1 ; record size = ptr(next record)
SUB.L D0,D1 ; - ptr(record) - (adj key length)
MOVEA.L A0,A1 ; ptr(data record) = ptr(key)
ADDA.L D0,A1 ; + (adj key length)
MOVEM.L (SP)+,D0/D2-D3 ; restore registers
RTS ; exit LocRec
;__________________________________________________________________________________
;
; Routine: LocTPR (Locate Tree Path Record)
;
; Function: Locates the Tree Path Record (TPR) for a given tree level.
;
; Input: D0.W - tree level
; A4.L - pointer to BTCB
;
; Output: A0.L - ptr(TPR)
;__________________________________________________________________________________
LocTPR
SUB.W #1,D0 ; offset
MULU #LenTPR,D0 ; ...from beg of table
MOVEA.L BTCVarPtr(A4),A0 ; ptr to BTree buffer
LEA BTVTPTable(A0,D0.L),A0 ; get ptr(TPR)
RTS
;__________________________________________________________________________________
;
; Routine: MovOffLt
;
; Function: Move offsets left within a single node.
;
; Input: D0.W - number of offsets
; D1.W - delta amount to be added to each offset
; A0.L - pointer to source offset
; A1.L - pointer to destination offset
;
; Output: none
;__________________________________________________________________________________
MovOffLt
MOVEM.L D0-D2/A0-A1,-(SP) ; save regs
@1 MOVE.W (A0)+,D2 ; *ptrDst++ = *ptrSrc++ + delta
ADD.W D1,D2
MOVE.W D2,(A1)+
DBF D0,@1
BRA.S MovOExit ; return
;__________________________________________________________________________________
;
; Routine: MovOffRt
;
; Function: Move offsets right within a single node.
;
; Input: D0.W - number of offsets
; D1.W - delta amount to be added to each offset
; A0.L - pointer to source offset
; A1.L - pointer to destination offset
;
; Output: none
;__________________________________________________________________________________
MovOffRt
MOVEM.L D0-D2/A0-A1,-(SP) ; save regs
CMPM.W (A0)+,(A1)+ ; preincrement A0, A1 for loop
@1 MOVE.W -(A0),D2 ; *ptrDst-- = *ptrSrc-- + delta
ADD.W D1,D2
MOVE.W D2,-(A1)
DBF D0,@1
MovOExit
MOVEM.L (SP)+,D0-D2/A0-A1 ; restore regs
RTS
;__________________________________________________________________________________
;
; Routine: MovRecLt
;
; Function: Move records left within a single node.
;
; Input: D0.W - number of bytes to move
; A0.L - pointer to source
; A1.L - pointer to destination
;
; Output: none
;__________________________________________________________________________________
MovRecLt
MOVEM.L D0-D1/A0-A1,-(SP) ; save regs
TST.W D0 ; test byte count
BLE.S MovlExit ; byte count <= 0
SUBQ.W #1,D0 ; adjust loop index
@1 MOVE.B (A0)+,(A1)+ ; move
DBRA D0,@1 ; ...it
MovlExit
MOVEM.L (SP)+,D0-D1/A0-A1 ; restore regs
RTS ; return
;__________________________________________________________________________________
;
; Routine: MovRecRt
;
; Function: Move records right within a single node.
;
; Input: D0.W - number of bytes
; A0.L - pointer to source
; A1.L - pointer to destination
;
; Output: none
;__________________________________________________________________________________
MovRecRt
MOVEM.L D0-D1/A0-A1,-(SP) ; save regs
TST.W D0
BLE.S MovrExit ; byte count <= 0
ADDA.W D0,A0 ; high-address of source block
ADDA.W D0,A1 ; high-address of dest block
SUBQ.W #1,D0 ; byte count - 1
@1 MOVE.B -(A0),-(A1) ; move
DBRA D0,@1 ; ...it
MovrExit
MOVEM.L (SP)+,D0-D1/A0-A1 ; restore regs
RTS ; return
;__________________________________________________________________________________
;
; Routine: RelNode
;
; Function: Releases use of a BTree node obtained by GetNode.
; Note: this is a temporary interface, it will change for the new
; cache.
;
; Input: A0.L - pointer to node buffer
; D1.B - RelBlock option flags
; A4.L - pointer to BTCB
;
; Output D0.W - result code
; 0 = ok
; -n = error
;
; Called by: BTInsert,BTDelete,BTGetRecord,BTSearch,TreeSearch
;__________________________________________________________________________________
RelNode
MOVE.L jRelNode,-(SP) ; jumptable entry for vRelNode <25Oct85>
RTS ; go there <25Oct85>
vRelNode ; 'vectored' RelNode routine <25Oct85>
MOVE.L (SP)+,-(A6) ; save return address on A6 stack
MOVE.L A1,-(A6) ; save registers
MOVE.L A0,D0 ; have a node to release? <23Sep85>
BEQ.S RNExit ; no -> <23Sep85>
IF HFSDebug THEN ; Only check when debugging <24Sep85>
TST.W NDNRecs(A0) ; empty node? <23Sep85>
BEQ.S @1 ; yes, skip node check <23Sep85>
MOVEA.L A0,A1 ; ***** check out the node ***** <21Sep85>
BSR ChkNode ; <21Sep85>
BEQ.S @1 ; ok -> <21Sep85>
_HFSDSErr ; *** HALT *** <24Sep85>
ENDIF
@1 JSR RelBlock ; release the block
RNExit
MOVE.L (A6)+,A1 ; restore registers
MOVE.L (A6)+,-(SP) ; put return address back on stack
TST.W D0 ; set up condition codes
RTS ; exit RelNode
;__________________________________________________________________________________
;
; Routine: SearchNode
;
; Function: Searches a BTree node for a specified key. A binary search
; algorithym is used.
;
; Input: A0.L - ptr(search key)
; A1.L - ptr(node buffer)
; A4.L - pointer to BTCB
;
; Output: D0.W - result code
; 0 = ok
; BTnotfound = record not found
; A1.L - ptr(node buffer)
; D1.W - index
; record index if found
; insert index if not found
;
; Called by: BTSearch,TreeSearch
;__________________________________________________________________________________
SearchNode
MOVEM.L D2-D5/A1-A3,-(SP) ; save regs
;
; set up some common stuff
;
MOVE.L A0,A3 ; A3 = ptr(search key)
MOVE.L A1,A2 ; A2 = ptr(node buffer)
MOVE.L BTCKeyCR(A4),D5 ; D5 = ptr(key compare routine)
;
; search node for key using a binary search
;
CLR.W D2 ; lower bnd = 0
MOVE.W NDNRecs(A2),D3 ; upper bnd = number of recs - 1
SUBQ.W #1,D3
CMP.W D3,D2 ; while lower bnd <= upper bnd
BGT.S SrchExit
SrchLoop
MOVE.W D2,D4 ; index = (upper+lower) / 2
ADD.W D3,D4 ;
LSR.W #1,D4 ; D4 = new index
MOVE.W D4,D0 ; get ptr(trial key)
MOVE.L A2,A1 ;
JSR GetRecA ;
MOVE.L A0,A1 ; A1 = ptr(trial key)
MOVEA.L A3,A0 ; A0 = ptr(search key)
MOVE.L A4,-(SP) ; save A4
MOVEA.L D5,A4 ; A4 = ptr(key compare routine)
JSR (A4) ; compare the keys
MOVE.L (SP)+,A4 ; restore A4
TST.W D0 ; test result code
BEQ.S SrchEQ ; search key = trial key ->
BGT.S SrchGT ; search key > trial key ->
SrchLT ; search key < trial key
MOVE.W D4,D3 ; upper = index - 1
SUBQ.W #1,D3
CMP.W D3,D2 ; upper <= lower ?
BLE.S SrchLoop
BRA.S SrchExit
SrchEQ
CLR.W D0 ; result = FOUND
BRA.S SrchRet
SrchGT
MOVE.W D4,D2 ; lower = index + 1
ADDQ.W #1,D2
CMP.W D3,D2 ; lower <= upper ?
BLE.S SrchLoop
SrchExit
MOVE.W D2,D4 ; index = lower
MOVEQ #BTnotfound,D0 ; result = 'not found' <14Oct85>
;
; clean up and exit
;
SrchRet
MOVE.W D4,D1 ; return index in D1
MOVEM.L (SP)+,D2-D5/A1-A3 ; restore regs
TST.W D0 ; set up condition codes
RTS ; exit SearchNode
;__________________________________________________________________________________
;
; Routine: UpdDRec (Update Data Record)
;
; Function: Updates the data portion of a BTree record.
;
; Input: A0.L - ptr(data record)
; 0 = create a null record (cleared to zero)
; D0.W - size of data record
; A1.L - ptr(node buffer) containing BTree record
; D1.W - index of BTree record
; A4.L - pointer to BTCB
;
; Output: none
;__________________________________________________________________________________
UpdDRec
MOVEM.L D0-D1/A0-A2,-(SP) ; save registers
MOVEA.L A0,A2 ; A2 = ptr(data record)
JSR LocRec ; locate data position in BTree record
MOVE.L A2,D1 ; ptr(data record)
BEQ.S @2 ; ptr = 0, clear the record ->
MOVEA.L D1,A0 ; source = data record
EXT.L D0 ; move length = record size
_BlockMove ; move in the data record
BRA.S UDExit ; all done ->
@1 CLR.B (A1)+ ; clear the record
@2 DBRA D0,@1 ;
UDExit
MOVEM.L (SP)+,D0-D1/A0-A2 ; restore registers
RTS ; exit UpdDRec
;__________________________________________________________________________________
;
; Routine: UpdIKey (Update Index Key)
;
; Function: Updates the key portion of an index record. Variable
; length source keys are padded with $00 to obtain a fixed
; length index key.
;
; Input: A0.L - pointer to source key
; A1.L - pointer to index record key
; A4.L - pointer to BTCB
;
; Output: A1.L - pointer to updated index record key
;__________________________________________________________________________________
UpdIKey
MOVEM.L D0-D1/A0-A2,-(SP) ; save regs
MOVEA.L A0,A2 ; save ptr(source key)
MOVE.W BTCKeyLen(A4),D1 ; get max key length
MOVE.B D1,(A1)+ ; stuff max key length
MOVEA.L A2,A0 ; ptr(source key)
MOVE.B (A0)+,D0 ; source key length
EXT.W D0 ;
SUB.W D0,D1 ; max key length - source key length
BGE.S @2 ; length ok, decrement before testing ->
ADD.W D1,D0 ; source > max, use max length
BRA.S @2 ;
@1 MOVE.B (A0)+,(A1)+ ; copy next byte
@2 DBF D0,@1 ;
TST.W D1 ; need any null padding?
BLE.S @5 ; no ->
BRA.S @4 ; decrement before testing
@3 CLR.B (A1)+ ; clear next byte in key (null pad)
@4 DBF D1,@3
@5 MOVEM.L (SP)+,D0-D1/A0-A2 ; restore regs
RTS ; exit UpdIKey
END
Reference in New Issue View Git Blame Copy Permalink