; ; tree.s ; ; Another attempt at symbol table management ; ; © 1995 Straylight ; ;----- Standard header ------------------------------------------------------ GET libs:header GET libs:swis GET libs:stream ;----- External dependencies ------------------------------------------------ GET sh.anchor GET sh.mem ;----- Main code ------------------------------------------------------------ AREA |TermScript$$Code|,CODE,READONLY ; --- tree_add --- ; ; On entry: R0 == type number ; R1 == address of name ; R2 == size of user data ; ; On exit: R0 == address of user data in new node ; CS if node already exists, else CC ; May return an error ; ; Use: Adds a node into a symbol table tree. EXPORT tree_add tree_add ROUT BIC R14,R14,#V_flag ;Assume no errors for now STMFD R13!,{R1-R5,R14} ;Save some registers ; --- Find a suitable place for the node --- LDR R5,sail_varTree ;Load base address of tree LDR R5,[R5] ;Because it's an anchor addr ADD R3,R5,R0,LSL #2 ;Find the appropriate root ; --- Keep on until we find a leaf --- 10tree_add LDR R4,[R3,#0] ;Load this offset CMP R4,#0 ;Was this a leaf item? BEQ %20tree_add ;Yes -- then we found the end ADD R4,R5,R4 ;Convert this to an address LDR R0,[R4,#tNode_name] ;Find this node's name offset ADD R0,R5,R0 ;Convert this to an address BL str_cmp ;Compare the strings ADDLT R3,R4,#tNode_right ;Less -- go right ADDGT R3,R4,#tNode_left ;More -- go left BNE %10tree_add ;If not a match, continue ADD R0,R4,#tNode_user ;Point to node's user data LDMFD R13!,{R1-R5,R14} ;Restore caller's registers ORRS PC,R14,#C_flag ;And tell him it was there ; --- Insert a new node --- 20tree_add SUB R3,R3,R5 ;Convert to an offset MOV R4,R1 ;Look after the name address 21tree_add LDRB R14,[R1],#1 ;Load a byte from the name CMP R14,#32 ;Is this the end yet? BCS %21tree_add ;No -- keep on going SUB R1,R1,R4 ;Work out the string length ADD R1,R1,#3+8 ;Now word align this size BIC R1,R1,#3 ;Tum te tum te tum ADD R2,R2,R1 ;Work out how much I need ; --- Extend the block --- ADR R14,sail_varPtr ;Find the block sizes LDMIA R14,{R0,R1} ;Load used and total length ADD R0,R0,R2 ;How much do I actually need? STR R0,sail_varPtr ;Save the updated value SUB R2,R0,R2 ;And get the original offset ADD R0,R0,#255 ;Align this to chunk size BIC R0,R0,#255 ;Pom pom pe pom pom... CMP R0,R1 ;Do we have enough? BLS %30tree_add ;Yes -- that's OK then ; --- Allocate some more memory --- MOV R1,R0 ;Get the new size I want LDR R0,sail_varTree ;Find the block's anchor BL mem_realloc ;Make the block bigger BVS %90tree_add ;If it failed, give up STR R1,sail_varSize ;Save the new size away ; --- Now we're ready to go --- 30tree_add MOV R1,R2 ;Look after this offset LDR R5,sail_varTree ;Find the tree base LDR R5,[R5] ;Irritating WimpExtension ADD R2,R5,R2 ;Turn offset into address 35tree_add LDRB R14,[R4],#1 ;Load a byte of the name CMP R14,#32 ;Is this the end yet? MOVCC R14,#0 ;Yes -- store final 0 STRB R14,[R2],#1 ;Store this byte away BCS %35tree_add ;And keep on going ADD R2,R2,#3 ;Word align output ptr BIC R2,R2,#3 ;Yawn-o-matic on a stick SUB R14,R2,R5 ;Work out the current offset STR R14,[R5,R3] ;Link this node into the tree MOV R3,R1 ;Find the string offset MOV R0,#0 ;Zero the left hand offset MOV R1,#0 ;And the right hand one STMIA R2,{R0,R1,R3} ;Fill in this node ADD R0,R2,#tNode_user ;Find the user data LDMFD R13!,{R1-R5,R14} ;Unstack caller's registers BICS PC,R14,#C_flag ;Say it wasn't there before ; --- Something went badly wrong --- 90tree_add LDMFD R13!,{R1-R5,R14} ;Unstack caller's registers ORRS PC,R14,#V_flag ;Return the error LTORG ; --- tree_find --- ; ; On entry: R0 == type number ; R1 == pointer to the name ; ; On exit: CS if the variable was found, and ; R0 == pointer to the variable block ; else CC and ; R0 corrupted ; ; Use: Tries to find a node with the given type and name in ; the symbol tree. EXPORT tree_find tree_find ROUT STMFD R13!,{R1-R5,R14} ;Save some registers ; --- Find a suitable place for the node --- LDR R5,sail_varTree ;Load base address of tree LDR R5,[R5] ;Because it's an anchor addr ADD R3,R5,R0,LSL #2 ;Find the appropriate root ; --- Keep on until we find a leaf --- 10tree_find LDR R4,[R3,#0] ;Load this offset CMP R4,#0 ;Was this a leaf item? BEQ %20tree_find ;Yes -- then we found the end ADD R4,R5,R4 ;Convert this to an address LDR R0,[R4,#tNode_name] ;Find this node's name offset ADD R0,R5,R0 ;Convert this to an address BL str_cmp ;Compare the strings ADDLT R3,R4,#tNode_right ;Less -- go right ADDGT R3,R4,#tNode_left ;More -- go left BNE %10tree_find ;If not a match, continue ADD R0,R4,#tNode_user ;Point to node's user data LDMFD R13!,{R1-R5,R14} ;Restore caller's registers ORRS PC,R14,#C_flag ;And tell him it was there ; --- Something went badly wrong --- 20tree_find LDMFD R13!,{R1-R5,R14} ;Unstack caller's registers BICS PC,R14,#C_flag ;Return `not found' LTORG ; --- str_cmp --- ; ; On entry: R0 == pointer to string A ; R1 == pointer to string B ; ; On exit: Flags as appropriate ; ; Use: Case-sensitively compares two strings. You can use the ; normal ARM condition codes after the compare, so you can ; treat this fairly much like a normal CMP. EXPORT str_cmp str_cmp ROUT STMFD R13!,{R0,R1,R3,R4,R14} 00str_cmp LDRB R3,[R0],#1 ;Get a character from A LDRB R4,[R1],#1 ;And one from B CMP R3,#&20 ;Is that the end of A? MOVLT R3,#0 ;Yes -- pretend it's null CMP R4,#&20 ;Is that the end of B? MOVLT R4,#0 ;Yes -- pretend it's null CMP R3,R4 ;How do they match up? LDMNEFD R13!,{R0,R1,R3,R4,PC} ;If NE, return condition CMP R3,#0 ;Is this the end? BNE %00str_cmp ;No -- loop again LDMFD R13!,{R0,R1,R3,R4,PC} ;Return to caller LTORG ; --- Tree node format --- ^ 0 tNode_left # 4 ;Left branch offset tNode_right # 4 ;Right branch offset tNode_user # 0 ;Start of user data area tNode_name # 4 ;Offset of name in table ;----- That's all, folks ---------------------------------------------------- END