chiark - git - mdw - ssr/blob - StraySrc/Libraries/Sapphire/sail/_s/tree

   1 ;
   2 ; tree.s
   3 ;
   4 ; Another attempt at symbol table management
   5 ;
   6 ; © 1995 Straylight
   7 ;
   8
   9 ;----- Standard header ------------------------------------------------------
  10
  11                 GET     libs:header
  12                 GET     libs:swis
  13
  14                 GET     libs:stream
  15
  16 ;----- External dependencies ------------------------------------------------
  17
  18                 GET     sh.anchor
  19                 GET     sh.mem
  20
  21 ;----- Main code ------------------------------------------------------------
  22
  23                 AREA    |TermScript$$Code|,CODE,READONLY
  24
  25 ; --- tree_add ---
  26 ;
  27 ; On entry:     R0 == type number
  28 ;               R1 == address of name
  29 ;               R2 == size of user data
  30 ;
  31 ; On exit:      R0 == address of user data in new node
  32 ;               CS if node already exists, else CC
  33 ;               May return an error
  34 ;
  35 ; Use:          Adds a node into a symbol table tree.
  36
  37                 EXPORT  tree_add
  38 tree_add        ROUT
  39
  40                 BIC     R14,R14,#V_flag         ;Assume no errors for now
  41                 STMFD   R13!,{R1-R5,R14}        ;Save some registers
  42
  43                 ; --- Find a suitable place for the node ---
  44
  45                 LDR     R5,tsc_varTree          ;Load base address of tree
  46                 LDR     R5,[R5]                 ;Because it's an anchor addr
  47                 ADD     R3,R5,R0,LSL #2         ;Find the appropriate root
  48
  49                 ; --- Keep on until we find a leaf ---
  50
  51 10tree_add      LDR     R4,[R3,#0]              ;Load this offset
  52                 CMP     R4,#0                   ;Was this a leaf item?
  53                 BEQ     %20tree_add             ;Yes -- then we found the end
  54                 ADD     R4,R5,R4                ;Convert this to an address
  55                 LDR     R0,[R4,#tNode_name]     ;Find this node's name offset
  56                 ADD     R0,R5,R0                ;Convert this to an address
  57                 BL      str_cmp                 ;Compare the strings
  58                 ADDLT   R3,R4,#tNode_right      ;Less -- go right
  59                 ADDGT   R3,R4,#tNode_left       ;More -- go left
  60                 BNE     %10tree_add             ;If not a match, continue
  61                 ADD     R0,R4,#tNode_user       ;Point to node's user data
  62                 LDMFD   R13!,{R1-R5,R14}        ;Restore caller's registers
  63                 ORRS    PC,R14,#C_flag          ;And tell him it was there
  64
  65                 ; --- Insert a new node ---
  66
  67 20tree_add      SUB     R3,R3,R5                ;Convert to an offset
  68                 MOV     R4,R1                   ;Look after the name address
  69 21tree_add      LDRB    R14,[R1],#1             ;Load a byte from the name
  70                 CMP     R14,#32                 ;Is this the end yet?
  71                 BCS     %21tree_add             ;No -- keep on going
  72                 SUB     R1,R1,R4                ;Work out the string length
  73                 ADD     R1,R1,#3+8              ;Now word align this size
  74                 BIC     R1,R1,#3                ;Tum te tum te tum
  75                 ADD     R2,R2,R1                ;Work out how much I need
  76
  77                 ; --- Extend the block ---
  78
  79                 ADR     R14,tsc_varPtr          ;Find the block sizes
  80                 LDMIA   R14,{R0,R1}             ;Load used and total length
  81                 ADD     R0,R0,R2                ;How much do I actually need?
  82                 STR     R0,tsc_varPtr           ;Save the updated value
  83                 SUB     R2,R0,R2                ;And get the original offset
  84                 ADD     R0,R0,#255              ;Align this to chunk size
  85                 BIC     R0,R0,#255              ;Pom pom pe pom pom...
  86                 CMP     R0,R1                   ;Do we have enough?
  87                 BLS     %30tree_add             ;Yes -- that's OK then
  88
  89                 ; --- Allocate some more memory ---
  90
  91                 MOV     R1,R0                   ;Get the new size I want
  92                 LDR     R0,tsc_varTree          ;Find the block's anchor
  93                 BL      mem_realloc             ;Make the block bigger
  94                 BVS     %90tree_add             ;If it failed, give up
  95                 STR     R1,tsc_varSize          ;Save the new size away
  96
  97                 ; --- Now we're ready to go ---
  98
  99 30tree_add      MOV     R1,R2                   ;Look after this offset
 100                 LDR     R5,tsc_varTree          ;Find the tree base
 101                 LDR     R5,[R5]                 ;Irritating WimpExtension
 102                 ADD     R2,R5,R2                ;Turn offset into address
 103 35tree_add      LDRB    R14,[R4],#1             ;Load a byte of the name
 104                 CMP     R14,#32                 ;Is this the end yet?
 105                 MOVCC   R14,#0                  ;Yes -- store final 0
 106                 STRB    R14,[R2],#1             ;Store this byte away
 107                 BCS     %35tree_add             ;And keep on going
 108                 ADD     R2,R2,#3                ;Word align output ptr
 109                 BIC     R2,R2,#3                ;Yawn-o-matic on a stick
 110
 111                 SUB     R14,R2,R5               ;Work out the current offset
 112                 STR     R14,[R5,R3]             ;Link this node into the tree
 113                 MOV     R3,R1                   ;Find the string offset
 114                 MOV     R0,#0                   ;Zero the left hand offset
 115                 MOV     R1,#0                   ;And the right hand one
 116                 STMIA   R2,{R0,R1,R3}           ;Fill in this node
 117                 ADD     R0,R2,#tNode_user       ;Find the user data
 118                 LDMFD   R13!,{R1-R5,R14}        ;Unstack caller's registers
 119                 BICS    PC,R14,#C_flag          ;Say it wasn't there before
 120
 121                 ; --- Something went badly wrong ---
 122
 123 90tree_add      LDMFD   R13!,{R1-R5,R14}        ;Unstack caller's registers
 124                 ORRS    PC,R14,#V_flag          ;Return the error
 125
 126                 LTORG
 127
 128 ; --- tree_find ---
 129 ;
 130 ; On entry:     R0 == type number
 131 ;               R1 == pointer to the name
 132 ;
 133 ; On exit:      CS if the variable was found, and
 134 ;                 R0 == pointer to the variable block
 135 ;               else CC and
 136 ;                 R0 corrupted
 137 ;
 138 ; Use:          Tries to find a node with the given type and name in
 139 ;               the symbol tree.
 140
 141                 EXPORT  tree_find
 142 tree_find       ROUT
 143
 144                 STMFD   R13!,{R1-R5,R14}        ;Save some registers
 145
 146                 ; --- Find a suitable place for the node ---
 147
 148                 LDR     R5,tsc_varTree          ;Load base address of tree
 149                 LDR     R5,[R5]                 ;Because it's an anchor addr
 150                 ADD     R3,R5,R0,LSL #2         ;Find the appropriate root
 151
 152                 ; --- Keep on until we find a leaf ---
 153
 154 10tree_find     LDR     R4,[R3,#0]              ;Load this offset
 155                 CMP     R4,#0                   ;Was this a leaf item?
 156                 BEQ     %20tree_find            ;Yes -- then we found the end
 157                 ADD     R4,R5,R4                ;Convert this to an address
 158                 LDR     R0,[R4,#tNode_name]     ;Find this node's name offset
 159                 ADD     R0,R5,R0                ;Convert this to an address
 160                 BL      str_cmp                 ;Compare the strings
 161                 ADDLT   R3,R4,#tNode_right      ;Less -- go right
 162                 ADDGT   R3,R4,#tNode_left       ;More -- go left
 163                 BNE     %10tree_find            ;If not a match, continue
 164
 165                 ADD     R0,R4,#tNode_user       ;Point to node's user data
 166                 LDMFD   R13!,{R1-R5,R14}        ;Restore caller's registers
 167                 ORRS    PC,R14,#C_flag          ;And tell him it was there
 168
 169                 ; --- Something went badly wrong ---
 170
 171 20tree_find     LDMFD   R13!,{R1-R5,R14}        ;Unstack caller's registers
 172                 BICS    PC,R14,#C_flag          ;Return `not found'
 173
 174                 LTORG
 175
 176 ; --- str_cmp ---
 177 ;
 178 ; On entry:     R0 == pointer to string A
 179 ;               R1 == pointer to string B
 180 ;
 181 ; On exit:      Flags as appropriate
 182 ;
 183 ; Use:          Case-sensitively compares two strings.  You can use the
 184 ;               normal ARM condition codes after the compare, so you can
 185 ;               treat this fairly much like a normal CMP.
 186
 187                 EXPORT  str_cmp
 188 str_cmp         ROUT
 189
 190                 STMFD   R13!,{R0,R1,R3,R4,R14}
 191 00str_cmp       LDRB    R3,[R0],#1              ;Get a character from A
 192                 LDRB    R4,[R1],#1              ;And one from B
 193                 CMP     R3,#&20                 ;Is that the end of A?
 194                 MOVLT   R3,#0                   ;Yes -- pretend it's null
 195                 CMP     R4,#&20                 ;Is that the end of B?
 196                 MOVLT   R4,#0                   ;Yes -- pretend it's null
 197                 CMP     R3,R4                   ;How do they match up?
 198                 LDMNEFD R13!,{R0,R1,R3,R4,PC}   ;If NE, return condition
 199                 CMP     R3,#0                   ;Is this the end?
 200                 BNE     %00str_cmp              ;No -- loop again
 201                 LDMFD   R13!,{R0,R1,R3,R4,PC}   ;Return to caller
 202
 203                 LTORG
 204
 205                 ; --- Tree node format ---
 206
 207                 ^       0
 208 tNode_left      #       4                       ;Left branch offset
 209 tNode_right     #       4                       ;Right branch offset
 210 tNode_user      #       0                       ;Start of user data area
 211 tNode_name      #       4                       ;Offset of name in table
 212
 213 ;----- That's all, folks ----------------------------------------------------
 214
 215                 END