; ; 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