Macintosh-SW/boot3
1
0
Fork 0
mirror of https://github.com/elliotnunn/boot3.git synced 2024-06-09 02:29:27 +00:00
Code Issues Projects Releases Wiki Activity
master
boot3/OS/HFS/BTMAINT2.a
Elliot Nunn 5b0f0cc134 Bring in CubeE sources 
Resource forks are included only for .rsrc files. These are DeRezzed into their data fork. 'ckid' resources, from the Projector VCS, are not included.

The Tools directory, containing mostly junk, is also excluded.
2017-12-26 10:02:57 +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