Mercurial > hg > index.cgi

comparison lwasm/symbol.c @ 195:17bd59f045af

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }