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

541 lines
16 KiB
Plaintext
Raw Permalink Blame History

;
; File: BTMAINT1.a
;
; Contains: These routines provide multiple-node BTree maintenance
; functions.
;
; Copyright: © 1984-1991 by Apple Computer, Inc., all rights reserved.
;
; Change History (most recent first):
;
; <2> 9/10/91 JSM Add a header.
; <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/27/86 BB Vectored TreeSearch routine.
; 9/25/86 BB Updated to use new MPW equate files.
; 12/19/85 BB SplitLt now checks for errors returned from InitNode (not
; patched in ROm75).
; 10/25/85 BB Made RotRecLt into an internal subroutine. It is only called by
; RotatLt.
; 10/10/85 BB Added use of new MOVEQ equates for GetBlock and RelBlock. Did
; some minor code clean up.
; 8/9/85 BB Modifed SplitLt to set up node height.
; 8/7/85 BB Added deep shit error call to RotateLt.
; 8/6/85 BB Updated to use equates for index and leaf node types.
; 8/4/85 BB Fixed fit calculation bug in RotateLt.
; 7/17/85 BB ReWorked rotate algorithm in RotateLT.
; 7/8/85 BB Modified SplitLt to maintain links for index nodes.
; 7/8/85 BB Modified TreeSearch to no longer set up left and right sibling
; node addresses in the TPT.
; 6/10/85 BB Cleaned up some.
; 3/15/85 BB Modified to use A6 stack.
; 2/25/85 BB Modified RotateLt and SplitLt to return the node number and
; record index of new (inserted) record.
; 1/17/85 BB Removed use of BTree Global area (BTG).
; 10/1/84 BB Split off from BTmaint.
;
;__________________________________________________________________________________
;
; External
; Routines: RotateLt - Inserts a record into a BTree node via rotation
; of records into the left sibling node.
; SplitLt - Inserts a new record into a BTree node by inserting
; an empty left node and then using RotateLt to insert
; the new record.
; TreeSearch - Searches BTree for a specified key setting up the
; Tree Path Table (TPT) to reflect the search path.
;
; Internal
; Subroutines: RotRecLt - Rotates one record from the right node into the
; left node.
;
;__________________________________________________________________________________
BLANKS ON
STRING ASIS
PRINT OFF
LOAD 'StandardEqu.d'
PRINT ON
PRINT NOGEN
BTMaint1 PROC EXPORT
EXPORT RotateLt,SplitLt,TreeSearch
EXPORT vTreeSearch ;<27Oct86>
IMPORT AllocNode
IMPORT GetNode,RelNode
IMPORT DeleteRec,GetNodeSiz,GetOffset,GetRecA,InitNode,InsertRec
IMPORT LocRec,LocTPR,MovOffLt,MovOffRt,MovRecLt,MovRecRt,SearchNode
;__________________________________________________________________________________
;
; Routine: RotateLt
;
; Function: Inserts a record into a BTree node via rotation of records
; into the left sibling node.
;
; Input: A0.L - pointer to record
; D0.W - size of record
; A2.L - pointer to left node buffer
; A3.L - pointer to right node buffer
; D1.W - index of insert point (in right node)
; A4.L - pointer to BTCB
;
; 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
MOVEM.L D2-D7/A2-A5,-(SP) ; save regs
;
; set up some common stuff
;
MOVEA.L A0,A5 ; A5 = ptr(new record)
MOVE.W D0,D5 ; D5 = size of new record
;
; calculate split point
;
MOVEA.L A2,A1 ; point to left node
JSR GetNodeSiz ; get its size
MOVE.W D0,D2 ; D2 = left node size
MOVEA.L A3,A1 ; point to right node
JSR GetNodeSiz ; get its size
ADD.W D2,D0 ; right size + left size
ADD.W D5,D0 ; + (new record size + 2)
ADDQ.W #2,D0 ; = total data size
LSR.W #1,D0 ; total size / 2 = split point
MOVE.W D0,D6 ; D6 = split point
;
; simulate left rotation to determine best fit
;
MOVE.W NDNRecs(A2),D3 ; D3 = init virt indx = #recs in lt node
MOVE.W D1,D4 ; D4 = virtual insert index
ADD.W D3,D4 ; = rt insert indx + #recs in lt node
MOVEQ #-1,D7 ; no current fit or previous fit
RLFitLoop
CMP.W D3,D4 ; at insert point ?
BNE.S @2 ; no, ->
ADD.W D5,D2 ; include new record in lt size
BRA.S @4 ; ->
@2 MOVE.W D3,D0 ; convert virtual index
SUB.W NDNRecs(A2),D0 ;
CMP.W D4,D3 ;
BLE.S @3 ;
SUBQ.W #1,D0 ; ...to a right node index
@3 JSR GetRecA ; get record size
ADD.W D0,D2 ; include record in lt size
@4 ADDQ.W #2,D2 ; include offset also
;
; check for a fit after simulated rotation of each record.
;
RLChkFit
MOVE.W BTCNodeSize(A4),D1 ; max node size
SUBI.W #(lenND+2),D1 ; - length(ND) - 2 = max data size
CMP.W D1,D2 ; left node fit?
BLE.S @1 ; yes ->
SWAP D7 ; have previous fit?
TST.W D7 ;
BGE.S RLRotate ; yes, use it ->
MOVEQ #-1,D0 ; result = 'won't fit'
BRA RLExit1 ; exit ->
@1 MOVE.W D6,D0 ; split point
LSL.W #1,D0 ; X 2 = total data size
SUB.W D2,D0 ; - lt size = rt size
CMP.W D1,D0 ; right node fit?
BGT.S RLCkSplit ; no ->
MOVE.W D3,D7 ; save virtual index for this fit
;
; select best fit if we have reached split point
;
RLCkSplit
CMP.W D6,D2 ; reached split point ?
BLT.S @2 ; no ->
BEQ.S @1 ; right on the money ->
SWAP D7 ; past split point, try previous fit first
@1 TST.W D7 ; have a fit?
BGE.S RLRotate ; yes, use it ->
SWAP D7 ; no, get previous fit
TST.W D7 ; have one?
BGE.S RLRotate ; yes, use it ->
@2 SWAP D7 ; previous fit = current fit
MOVE.W #-1,D7 ; no current fit
ADDQ.W #1,D3 ; bump index to next record
MOVE.W NDNRecs(A2),D1 ; max virtual index
ADD.W NDNRecs(A3),D1 ; = #recs in lt node + #recs in rt node
CMP.W D1,D3 ; any more records?
BLE.S RLFitLoop ; yes, keep trying ->
MOVEQ #-1,D0 ; result = 'won't fit'
BRA.S RLExit1 ; exit ->
;
; we have a fit, do the actual rotation
;
RLRotate
MOVE.W NDNRecs(A2),D3 ; init virt indx = 1st rec in rt node
@1 CMP.W D3,D4 ; at insert point ?
BNE.S @2 ; no ->
MOVEA.L A2,A1 ; ptr(left node)
MOVEA.L A5,A0 ; ptr(new record)
MOVE.W D5,D0 ; size of new record
MOVE.W NDNRecs(A1),D1 ; insert index = end of node
JSR InsertRec ; insert new record in left node
BNE.S RLDeepShit ; trouble ->
MOVEA.L A1,A5 ; save ptr(node buffer) and index
MOVE.W D1,D5 ; ...for new record
BRA.S @3 ; ->
@2 MOVEA.L A2,A0 ; ptr(left node)
MOVEA.L A3,A1 ; ptr(right node)
BSR RotRecLt ; rotate 1st record in right node
BNE.S RLDeepShit ; trouble ->
@3 CMP.W D7,D3 ; reached split index ?
BEQ.S RLCheckRt ; yes ->
ADDQ.W #1,D3 ; bump record index
BRA.S @1 ; rotate another one ->
;
; check if new record goes in right node
;
RLCheckRt
CMP.W D7,D4 ; insert index > split index ?
BLE.S RLExit ; no, not in right node ->
MOVEA.L A3,A1 ; ptr(right node)
MOVEA.L A5,A0 ; ptr(new record)
MOVE.W D5,D0 ; size of new record
MOVE.W D4,D1 ; insert index
SUB.W D7,D1 ; = virt insert index
SUBQ.W #1,D1 ; - split index - 1
JSR InsertRec ; insert new record in right node
BNE.S RLDeepShit ; all done ->
CLR.W D0 ; result = 'ok'
BRA.S RLExit1 ; exit ->
RLDeepShit
MOVEQ #dsBadRotate,D0 ; result = 'bad rotate'
_SysError ; give up
;
; clean up and exit
;
RLExit
CLR.W D0 ; result = ok
MOVEA.L A5,A1 ; return ptr(node buffer) and index
MOVE.W D5,D1 ; ...for new record
RLExit1
MOVEM.L (SP)+,D2-D7/A2-A5 ; restore regs
TST.W D0 ; set condition codes
RTS ; exit RotateLt
;__________________________________________________________________________________
;
; Routine: SplitLt (Split Left)
;
; Function: Inserts a new record into a BTree node by first inserting a
; empty left node and then using RotateLt to insert the new
; record.
;
; Input: A0.L - ptr(record)
; D0.W - size of record
; A2.L - pointer to left node buffer
; 0 = no left node
; A3.L - pointer to right node buffer
; D1.W - index of insert point (in right node)
; A4.L - pointer to BTCB
;
; Output: D0.W - result code
; 0 = ok
; +1 = won't fit
; -n = IO error
; A1.L - ptr(node buffer) containing new record
; D1.W - index of new record
; A2.L - ptr(new left node)
; D2.L - node number of new left node
;
; Called by: BTInsert
;__________________________________________________________________________________
SplitLt
MOVE.L (SP)+,-(A6) ; save return address on A6 stack
MOVEM.L D3-D7/A3,-(A6) ; save regs
;
; set up some common stuff
;
MOVE.L A0,D7 ; D7 = ptr(record)
MOVE.W D0,D6 ; D6 = size of record
MOVE.W D1,D5 ; D5 = insert index
MOVE.W BTCLevel(A4),D0 ; locate TPR
JSR LocTPR ; ... for current level
MOVE.L TPRNodeN(A0),D4 ; D4 = right node number
;
; allocate a new disk node
;
MOVE.W BTCRefNum(A4),D0 ; volume refnum
JSR AllocNode ; allocate the node
BNE.S SLExit1 ; error ->
MOVE.L D1,D3 ; D3 = new left node number
;
; update forward link in original left node and release it
;
MOVE.L A2,D0 ; have a left node ?
BEQ.S SLInit ; no ->
MOVE.L D3,NDFlink(A2) ; left forward link = new node number
MOVEQ #kRBDirty,D1 ; indicate dirty buffer <10Oct85>
MOVEA.L A2,A0 ; ptr(left node buffer)
JSR RelNode ; release left node
BNE.S SLExit1 ; error ->
;
; initialize a new left node
;
SLInit
MOVE.L D3,D1 ; new node number
JSR InitNode ; get an initialized node
BNE.S SLExit1 ; error -> <19Dec85>
MOVEA.L A0,A2 ; A2 = ptr(new left node)
MOVE.B NDType(A3),NDType(A2) ; set to same type as right node
MOVE.L NDBlink(A3),NDBlink(A2) ; finish updating
MOVE.L D4,NDFlink(A2) ;...
MOVE.L D3,NDBlink(A3) ;... links
MOVEQ #1,D0 ; node height
ADD.W BTCDepth(A4),D0 ; = tree depth + 1
SUB.W BTCLevel(A4),D0 ; - current level
MOVE.B D0,NDNHeight(A2) ;
CMPI.B #NDLeafNode,NDType(A2) ; adding a new leaf node?
BNE.S SLRotate ; no ->
TST.L NDBlink(A2) ; new 1st node?
BNE.S SLRotate ; no ->
MOVE.L D3,BTCFNode(A4) ; yes, update 1st node pointer
;
; insert new record via rotate left
;
SLRotate
MOVEA.L D7,A0 ; ptr(new record)
MOVE.W D6,D0 ; size of new record
MOVE.W D5,D1 ; insert index
JSR RotateLT ; insert via rotate left
BEQ.S SLExit ; ok ->
BRA.S SLExit1 ; oh shit!!!
;
; clean up and exit
;
SLExit
CLR.W D0 ; result = ok
MOVE.L D3,D2 ; return left node number in D2
SLExit1
MOVEM.L (A6)+,D3-D7/A3 ; restore regs
MOVE.L (A6)+,-(SP) ; put return address back on stack
TST.W D0 ; set condition codes
RTS ; exit SplitLt
;__________________________________________________________________________________
;
; Routine: TreeSearch
;
; Function: Searches BTree for a specified key, setting up the Tree Path
; Table (TPR) to reflect the search path.
;
; Input: A0.L - ptr(search key)
; A4.L - pointer to BTCB
;
; Output: D0.W - result code
; 0 = ok (record found)
; BTnotfound = record not found
; other = error
; A1.L - ptr(node buffer)
; D1.W - index
; record index if found
; insert index if not found
; D2.L - node number of target leaf node
;
; Called by: BTDelete,BTInsert,BTSearch
;__________________________________________________________________________________
TreeSearch
MOVE.L jTreeSearch,-(SP) ; jump table entry for vTreeSearch <27Oct86>
RTS ; go there <27Oct86>
vTreeSearch ; 'vectored' TreeSearch routine <27Oct86>
MOVE.L (SP)+,-(A6) ; save return address on A6 stack
MOVEM.L D3-D7/A2-A3,-(A6) ; save regs
;
; set up some common stuff
;
MOVE.L A0,D7 ; D7 = ptr(search key)
TST.W BTCDepth(A4) ; tree empty ?
BGT.S @1 ; no ->
MOVEQ #BTnotfound,D0 ; result = 'not found' <14Oct85>
SUBA.L A1,A1 ; no node buffer
CLR.L D1 ; index = 0
CLR.L D2 ; node number = 0
CLR.W BTCLevel(A4) ; current level = 0
BRA.S TSExit ; exit ->
@1 MOVEQ #1,D6 ; start at level 1
MOVE.L BTCRoot(A4),D3 ; root node number
;
; get the node and search for key
;
TSLoop
MOVEQ #0,D1 ; no GetBlock options <10Oct85>
MOVE.L D3,D2 ; node number
JSR GetNode ; get the node
BNE.S TSExit ; error ->
MOVEA.L A0,A1 ; A1 = ptr(node buffer)
MOVEA.L D7,A0 ; ptr(search key)
JSR SearchNode ; search node for key
MOVE.W D0,D5 ; D5 = search result
MOVE.W D1,D4 ; D4 = index
;
; update up TPR info
;
TSUpdTPR
MOVE.W D6,D0 ; locate TPR
JSR LocTPR ; ...for this level
MOVEA.L A0,A3 ; A3 = ptr(TPR)
MOVE.L D3,TPRNodeN(A3) ; set node number
MOVE.W D4,D2 ; assume parent index = insert index
TST.W D5 ; key found ?
BEQ.S @1 ; yes ->
SUBQ.W #1,D2 ; parent index = insert index - 1
BGE.S @1 ; parent index >= 0, ok ->
MOVE.W D4,D2 ; use insert index
@1 MOVE.W D2,TPRRIndx(A3) ; set record index
CMP.W BTCDepth(A4),D6 ; at leaf level ?
BEQ.S TSDone ; yes, all done ->
;
; move to next level down
;
TSNxtLev
MOVE.W D2,D1 ; parent index <10Oct85>
MOVE.L A1,-(SP) ; save ptr to node buffer <10Oct85>
JSR LocRec ; locate child record <10Oct85>
MOVE.L (A1),D3 ; D3 = child node number <10Oct85>
MOVEA.L (SP)+,A1 ; restore ptr to node buffer <10Oct85>
MOVEQ #0,D1 ; no RelBlock options <10Oct85>
MOVEA.L A1,A0 ; ptr(node buffer)
JSR RelNode ; release current node
ADDQ.W #1,D6 ; bump level count
BRA.S TSLoop ; continue the search
;
; at leaf level set up return info
;
TSDone
MOVE.W D6,BTCLevel(A4) ; initialize current level
MOVE.W D4,D1 ; return insert index in D1
MOVE.W D5,D0 ; return search result in D0
MOVE.L D3,D2 ; return node number in D2
TSExit
MOVEM.L (A6)+,D3-D7/A2-A3 ; restore regs
MOVE.L (A6)+,-(SP) ; put return address back on stack
TST.W D0 ; set up condition codes
RTS ; exit TreeSearch
;__________________________________________________________________________________
;
; Internal Subroutines
;__________________________________________________________________________________
;__________________________________________________________________________________
;
; Routine: RotRecLt
;
; Function: Rotates one record from the right node into the left node.
;
; Input: A0.L - ptr(left node)
; A1.L - ptr(right node)
;
; Output: D0.W - result code
; 0 = ok
; -1 = won't fit
;
; Called by: RotateLT
;__________________________________________________________________________________
RotRecLt
MOVEM.L A2-A3,-(SP) ; save registers
;
; insert first record of right node at the end of the left node
;
MOVEA.L A0,A2 ; A2 = ptr(lt node)
MOVEA.L A1,A3 ; A3 = ptr(rt node)
MOVEQ #0,D0 ; index of 1st record
JSR GetRecA ; get the record size
LEA lenND(A1),A0 ; ptr(1st record) in rt node
MOVEA.L A2,A1 ; A1 = ptr(left node)
MOVE.W NDNRecs(A1),D1 ; insert index into left node
JSR InsertRec ; insert record in left node
MOVEA.L A3,A1 ; A1 = ptr(right node)
BEQ.S RRLDelete ; insert ok ->
MOVEQ #-1,D0 ; result = "won't fit"
BRA.S RRLExit ; exit ->
;
; delete record from right node
;
RRLDelete
CLR.W D1 ; index = 0
JSR DeleteRec ; delete it
CLR.W D0 ; result = ok
RRLExit
TST.W D0 ; set condition codes
MOVEM.L (SP)+,A2-A3 ; restore registers
RTS ; exit RotRecLt
END
Reference in New Issue View Git Blame Copy Permalink