Mercurial > hg > index.cgi
comparison lwasm/symbol.c @ 195:17bd59f045af
Changed symbol table to use a binary tree.
Changed symbol table to use a binary tree. Hopefully this improves table
lookups some but the tree really needs to be balanced at some point.
author | William Astle <lost@l-w.ca> |
---|---|
date | Sun, 11 Mar 2012 16:05:54 -0600 |
parents | ed7f970f3688 |
children | 080bb67d84f2 |
comparison
equal
deleted
inserted
replaced
194:f8b33b3a45ac | 195:17bd59f045af |
---|---|
27 #include <lw_expr.h> | 27 #include <lw_expr.h> |
28 #include <lw_string.h> | 28 #include <lw_string.h> |
29 | 29 |
30 #include "lwasm.h" | 30 #include "lwasm.h" |
31 | 31 |
32 #if 0 | |
32 struct symtabe *symbol_findprev(asmstate_t *as, struct symtabe *se) | 33 struct symtabe *symbol_findprev(asmstate_t *as, struct symtabe *se) |
33 { | 34 { |
34 struct symtabe *se1, *se2; | 35 struct symtabe *se1, *se2; |
35 int i; | 36 int i; |
36 | 37 |
70 | 71 |
71 se2 = se1; | 72 se2 = se1; |
72 } | 73 } |
73 return se2; | 74 return se2; |
74 } | 75 } |
75 | 76 #endif |
76 struct symtabe *register_symbol(asmstate_t *as, line_t *cl, char *sym, lw_expr_t val, int flags) | 77 struct symtabe *register_symbol(asmstate_t *as, line_t *cl, char *sym, lw_expr_t val, int flags) |
77 { | 78 { |
78 struct symtabe *se; | 79 struct symtabe *se, *nse; |
79 struct symtabe *sprev; | 80 struct symtabe *sprev; |
80 int islocal = 0; | 81 int islocal = 0; |
81 int context = -1; | 82 int context = -1; |
82 int version = -1; | 83 int version = -1; |
83 char *cp; | 84 char *cp; |
84 | 85 int cdir; |
86 | |
85 debug_message(as, 200, "Register symbol %s (%02X), %s", sym, flags, lw_expr_print(val)); | 87 debug_message(as, 200, "Register symbol %s (%02X), %s", sym, flags, lw_expr_print(val)); |
86 | 88 |
87 if (!(flags & symbol_flag_nocheck)) | 89 if (!(flags & symbol_flag_nocheck)) |
88 { | 90 { |
89 if (!sym || !*sym) | 91 if (!sym || !*sym) |
121 | 123 |
122 if (islocal) | 124 if (islocal) |
123 context = cl -> context; | 125 context = cl -> context; |
124 | 126 |
125 // first, look up symbol to see if it is already defined | 127 // first, look up symbol to see if it is already defined |
126 for (se = as -> symtab.head; se; se = se -> next) | 128 cdir = 0; |
127 { | 129 for (se = as -> symtab.head, sprev = NULL; se; ) |
128 debug_message(as, 300, "Symbol add lookup: %p, %p", se, se -> next); | 130 { |
129 if (!strcmp(sym, se -> symbol)) | 131 int ndir; |
130 { | 132 debug_message(as, 300, "Symbol add lookup: %p", se); |
131 if (se -> context != context) | 133 ndir = strcmp(sym, se->symbol); |
132 continue; | 134 if (!ndir && se -> context != context) |
135 { | |
136 ndir = (context < se -> context) ? -1 : 1; | |
137 } | |
138 if (!ndir) | |
139 { | |
133 if ((flags & symbol_flag_set) && (se -> flags & symbol_flag_set)) | 140 if ((flags & symbol_flag_set) && (se -> flags & symbol_flag_set)) |
134 { | 141 { |
135 if (version < se -> version) | 142 version = se -> version; |
136 version = se -> version; | |
137 continue; | |
138 } | 143 } |
139 break; | 144 break; |
140 } | 145 } |
141 } | 146 cdir = ndir; |
142 | 147 sprev = se; |
143 if (se) | 148 if (cdir < 0) |
149 se = se -> left; | |
150 else | |
151 se = se -> right; | |
152 } | |
153 | |
154 if (se && version == -1) | |
144 { | 155 { |
145 // multiply defined symbol | 156 // multiply defined symbol |
146 lwasm_register_error(as, cl, "Multiply defined symbol (%s)", sym); | 157 lwasm_register_error(as, cl, "Multiply defined symbol (%s)", sym); |
147 return NULL; | 158 return NULL; |
148 } | 159 } |
154 | 165 |
155 // symplify the symbol expression - replaces "SET" symbols with | 166 // symplify the symbol expression - replaces "SET" symbols with |
156 // symbol table entries | 167 // symbol table entries |
157 lwasm_reduce_expr(as, val); | 168 lwasm_reduce_expr(as, val); |
158 | 169 |
159 se = lw_alloc(sizeof(struct symtabe)); | 170 nse = lw_alloc(sizeof(struct symtabe)); |
160 se -> context = context; | 171 nse -> context = context; |
161 se -> version = version; | 172 nse -> version = version; |
162 se -> flags = flags; | 173 nse -> flags = flags; |
163 if (CURPRAGMA(cl, PRAGMA_NOLIST)) | 174 if (CURPRAGMA(cl, PRAGMA_NOLIST)) |
164 { | 175 { |
165 se -> flags |= symbol_flag_nolist; | 176 nse -> flags |= symbol_flag_nolist; |
166 } | 177 } |
167 se -> value = lw_expr_copy(val); | 178 nse -> value = lw_expr_copy(val); |
168 se -> symbol = lw_strdup(sym); | 179 nse -> symbol = lw_strdup(sym); |
180 nse -> right = NULL; | |
181 nse -> left = NULL; | |
182 nse -> nextver = NULL; | |
183 if (se) | |
184 { | |
185 nse -> nextver = se; | |
186 nse -> left = se -> left; | |
187 nse -> right = se -> right; | |
188 se -> left = NULL; | |
189 se -> right = NULL; | |
190 } | |
169 if (cl) | 191 if (cl) |
170 se -> section = cl -> csect; | 192 nse -> section = cl -> csect; |
171 else | 193 else |
172 se -> section = NULL; | 194 nse -> section = NULL; |
173 sprev = symbol_findprev(as, se); | |
174 if (!sprev) | 195 if (!sprev) |
175 { | 196 { |
176 debug_message(as, 200, "Adding symbol at head of symbol table"); | 197 debug_message(as, 200, "Adding symbol at head of symbol table"); |
177 se -> next = as -> symtab.head; | 198 as -> symtab.head = nse; |
178 as -> symtab.head = se; | |
179 } | 199 } |
180 else | 200 else |
181 { | 201 { |
182 debug_message(as, 200, "Adding symbol in middle of symbol table"); | 202 debug_message(as, 200, "Adding symbol in middle of symbol table"); |
183 se -> next = sprev -> next; | 203 if (cdir < 0) |
184 sprev -> next = se; | 204 sprev -> left = nse; |
185 } | 205 else |
186 return se; | 206 sprev -> right = nse; |
207 } | |
208 return nse; | |
187 } | 209 } |
188 | 210 |
189 // for "SET" symbols, always returns the LAST definition of the | 211 // for "SET" symbols, always returns the LAST definition of the |
190 // symbol. This works because the lwasm_reduce_expr() call in | 212 // symbol. This works because the lwasm_reduce_expr() call in |
191 // register_symbol will ensure there are no lingering "var" references | 213 // register_symbol will ensure there are no lingering "var" references |
197 // itself inside a "set" definition will refer to the previous version | 219 // itself inside a "set" definition will refer to the previous version |
198 // of the symbol. | 220 // of the symbol. |
199 struct symtabe * lookup_symbol(asmstate_t *as, line_t *cl, char *sym) | 221 struct symtabe * lookup_symbol(asmstate_t *as, line_t *cl, char *sym) |
200 { | 222 { |
201 int local = 0; | 223 int local = 0; |
202 struct symtabe *s, *s2; | 224 struct symtabe *s; |
203 | 225 int cdir; |
226 | |
204 // check if this is a local symbol | 227 // check if this is a local symbol |
205 if (strchr(sym, '@') || strchr(sym, '?')) | 228 if (strchr(sym, '@') || strchr(sym, '?')) |
206 local = 1; | 229 local = 1; |
207 | 230 |
208 if (cl && !CURPRAGMA(cl, PRAGMA_DOLLARNOTLOCAL) && strchr(sym, '$')) | 231 if (cl && !CURPRAGMA(cl, PRAGMA_DOLLARNOTLOCAL) && strchr(sym, '$')) |
212 | 235 |
213 // cannot look up local symbol in global context!!!!! | 236 // cannot look up local symbol in global context!!!!! |
214 if (!cl && local) | 237 if (!cl && local) |
215 return NULL; | 238 return NULL; |
216 | 239 |
217 for (s = as -> symtab.head, s2 = NULL; s; s = s -> next) | 240 for (s = as -> symtab.head; s; ) |
218 { | 241 { |
219 if (!strcmp(sym, s -> symbol)) | 242 cdir = strcmp(sym, s->symbol); |
243 if (!cdir) | |
220 { | 244 { |
221 if (local && s -> context != cl -> context) | 245 if (local && s -> context != cl -> context) |
222 continue; | 246 { |
223 | 247 cdir = (cl -> context < s -> context) ? -1 : 1; |
224 if (s -> flags & symbol_flag_set) | 248 } |
225 { | 249 } |
226 // look for highest version of symbol | 250 |
227 if (!s2 || (s -> version > s2 -> version)) | 251 if (!cdir) |
228 s2 = s; | 252 return s; |
229 continue; | 253 |
230 } | 254 if (cdir < 0) |
231 break; | 255 s = s -> left; |
232 } | 256 else |
233 } | 257 s = s -> right; |
234 if (!s && s2) | 258 } |
235 s = s2; | 259 return NULL; |
236 | |
237 return s; | |
238 } | 260 } |
239 | 261 |
240 struct listinfo | 262 struct listinfo |
241 { | 263 { |
242 sectiontab_t *sect; | 264 sectiontab_t *sect; |
266 } | 288 } |
267 } | 289 } |
268 return 0; | 290 return 0; |
269 } | 291 } |
270 | 292 |
271 void list_symbols(asmstate_t *as, FILE *of) | 293 void list_symbols_aux(asmstate_t *as, FILE *of, struct symtabe *se) |
272 { | 294 { |
273 struct symtabe *s; | 295 struct symtabe *s; |
274 lw_expr_t te; | 296 lw_expr_t te; |
275 struct listinfo li; | 297 struct listinfo li; |
276 | 298 |
277 li.as = as; | 299 li.as = as; |
278 | 300 |
279 fprintf(of, "\nSymbol Table:\n"); | 301 if (!se) |
280 | 302 return; |
281 for (s = as -> symtab.head; s; s = s -> next) | 303 |
282 { | 304 list_symbols_aux(as, of, se -> left); |
305 | |
306 for (s = se; s; s = s -> nextver) | |
307 { | |
283 if (s -> flags & symbol_flag_nolist) | 308 if (s -> flags & symbol_flag_nolist) |
284 continue; | 309 continue; |
285 lwasm_reduce_expr(as, s -> value); | 310 lwasm_reduce_expr(as, s -> value); |
286 fputc('[', of); | 311 fputc('[', of); |
287 if (s -> flags & symbol_flag_set) | 312 if (s -> flags & symbol_flag_set) |
330 fprintf(of, "<<incomplete>>\n"); | 355 fprintf(of, "<<incomplete>>\n"); |
331 // fprintf(of, "%s\n", lw_expr_print(s -> value)); | 356 // fprintf(of, "%s\n", lw_expr_print(s -> value)); |
332 } | 357 } |
333 lw_expr_destroy(te); | 358 lw_expr_destroy(te); |
334 } | 359 } |
335 } | 360 |
361 list_symbols_aux(as, of, se -> right); | |
362 } | |
363 | |
364 void list_symbols(asmstate_t *as, FILE *of) | |
365 { | |
366 fprintf(of, "\nSymbol Table:\n"); | |
367 list_symbols_aux(as, of, as -> symtab.head); | |
368 } |