Mercurial > hg-old > index.cgi

comparison old-trunk/lwlink/expr.c @ 339:eb230fa7d28e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Prepare for migration to hg
author lost
date Fri, 19 Mar 2010 02:54:14 +0000
parents
children
comparison
equal deleted inserted replaced
338:e7885b3ee266 339:eb230fa7d28e
1 /*
2 expr.c
3 Copyright © 2009 William Astle
4
5 This file is part of LWLINK.
6
7 LWLINK is free software: you can redistribute it and/or modify it under the
8 terms of the GNU General Public License as published by the Free Software
9 Foundation, either version 3 of the License, or (at your option) any later
10 version.
11
12 This program is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 more details.
16
17 You should have received a copy of the GNU General Public License along with
18 this program. If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 /*
22 This file contains the actual expression evaluator
23 */
24
25 #define __expr_c_seen__
26 #include <config.h>
27
28 #include <ctype.h>
29 #include <stdlib.h>
30 #include <string.h>
31
32 #include "expr.h"
33 #include "util.h"
34
35 lw_expr_stack_t *lw_expr_stack_create(void)
36 {
37 lw_expr_stack_t *s;
38
39 s = lw_malloc(sizeof(lw_expr_stack_t));
40 s -> head = NULL;
41 s -> tail = NULL;
42 return s;
43 }
44
45 void lw_expr_stack_free(lw_expr_stack_t *s)
46 {
47 while (s -> head)
48 {
49 s -> tail = s -> head;
50 s -> head = s -> head -> next;
51 lw_expr_term_free(s -> tail -> term);
52 lw_free(s -> tail);
53 }
54 lw_free(s);
55 }
56
57 lw_expr_stack_t *lw_expr_stack_dup(lw_expr_stack_t *s)
58 {
59 lw_expr_stack_node_t *t;
60 lw_expr_stack_t *s2;
61
62 s2 = lw_expr_stack_create();
63 for (t = s -> head; t; t = t -> next)
64 {
65 lw_expr_stack_push(s2, t -> term);
66 }
67 return s2;
68 }
69
70 void lw_expr_term_free(lw_expr_term_t *t)
71 {
72 if (t)
73 {
74 if (t -> term_type == LW_TERM_SYM)
75 lw_free(t -> symbol);
76 lw_free(t);
77 }
78 }
79
80 lw_expr_term_t *lw_expr_term_create_oper(int oper)
81 {
82 lw_expr_term_t *t;
83
84 t = lw_malloc(sizeof(lw_expr_term_t));
85 t -> term_type = LW_TERM_OPER;
86 t -> value = oper;
87 return t;
88 }
89
90 lw_expr_term_t *lw_expr_term_create_int(int val)
91 {
92 lw_expr_term_t *t;
93
94 t = lw_malloc(sizeof(lw_expr_term_t));
95 t -> term_type = LW_TERM_INT;
96 t -> value = val;
97 return t;
98 }
99
100 lw_expr_term_t *lw_expr_term_create_sym(char *sym, int symtype)
101 {
102 lw_expr_term_t *t;
103
104 t = lw_malloc(sizeof(lw_expr_term_t));
105 t -> term_type = LW_TERM_SYM;
106 t -> symbol = lw_strdup(sym);
107 t -> value = symtype;
108 return t;
109 }
110
111 lw_expr_term_t *lw_expr_term_dup(lw_expr_term_t *t)
112 {
113 switch (t -> term_type)
114 {
115 case LW_TERM_INT:
116 return lw_expr_term_create_int(t -> value);
117
118 case LW_TERM_OPER:
119 return lw_expr_term_create_oper(t -> value);
120
121 case LW_TERM_SYM:
122 return lw_expr_term_create_sym(t -> symbol, t -> value);
123
124 default:
125 exit(1);
126 }
127 // can't get here
128 }
129
130 void lw_expr_stack_push(lw_expr_stack_t *s, lw_expr_term_t *t)
131 {
132 lw_expr_stack_node_t *n;
133
134 if (!s)
135 {
136 exit(1);
137 }
138
139 n = lw_malloc(sizeof(lw_expr_stack_node_t));
140 n -> next = NULL;
141 n -> prev = s -> tail;
142 n -> term = lw_expr_term_dup(t);
143
144 if (s -> head)
145 {
146 s -> tail -> next = n;
147 s -> tail = n;
148 }
149 else
150 {
151 s -> head = n;
152 s -> tail = n;
153 }
154 }
155
156 lw_expr_term_t *lw_expr_stack_pop(lw_expr_stack_t *s)
157 {
158 lw_expr_term_t *t;
159 lw_expr_stack_node_t *n;
160
161 if (!(s -> tail))
162 return NULL;
163
164 n = s -> tail;
165 s -> tail = n -> prev;
166 if (!(n -> prev))
167 {
168 s -> head = NULL;
169 }
170
171 t = n -> term;
172 n -> term = NULL;
173
174 lw_free(n);
175
176 return t;
177 }
178
179 /*
180 take an expression stack s and scan for operations that can be completed
181
182 return -1 on error, 0 on no error
183
184 possible errors are: division by zero or unknown operator
185
186 theory of operation:
187
188 scan the stack for an operator which has two constants preceding it (binary)
189 or 1 constant preceding it (unary) and if found, perform the calculation
190 and replace the operator and its operands with the result
191
192 repeat the scan until no futher simplications are found or if there are no
193 further operators or only a single term remains
194
195 */
196 int lw_expr_reval(lw_expr_stack_t *s, lw_expr_stack_t *(*sfunc)(char *sym, int stype, void *state), void *state)
197 {
198 lw_expr_stack_node_t *n, *n2;
199 lw_expr_stack_t *ss;
200 int c;
201
202 next_iter_sym:
203 // resolve symbols
204 // symbols that do not resolve to an expression are left alone
205 for (c = 0, n = s -> head; n; n = n -> next)
206 {
207 if (n -> term -> term_type == LW_TERM_SYM)
208 {
209 ss = sfunc(n -> term -> symbol, n -> term -> value, state);
210 if (ss)
211 {
212 c++;
213 // splice in the result stack
214 if (n -> prev)
215 {
216 n -> prev -> next = ss -> head;
217 }
218 else
219 {
220 s -> head = ss -> head;
221 }
222 ss -> head -> prev = n -> prev;
223 ss -> tail -> next = n -> next;
224 if (n -> next)
225 {
226 n -> next -> prev = ss -> tail;
227 }
228 else
229 {
230 s -> tail = ss -> tail;
231 }
232 lw_expr_term_free(n -> term);
233 lw_free(n);
234 n = ss -> tail;
235
236 ss -> head = NULL;
237 ss -> tail = NULL;
238 lw_expr_stack_free(ss);
239 }
240 }
241 }
242 if (c)
243 goto next_iter_sym;
244
245 next_iter:
246 // a single term
247 if (s -> head == s -> tail)
248 return 0;
249
250 // search for an operator
251 for (n = s -> head; n; n = n -> next)
252 {
253 if (n -> term -> term_type == LW_TERM_OPER)
254 {
255 if (n -> term -> value == LW_OPER_NEG
256 || n -> term -> value == LW_OPER_COM
257 )
258 {
259 // unary operator
260 if (n -> prev && n -> prev -> term -> term_type == LW_TERM_INT)
261 {
262 // a unary operator we can resolve
263 // we do the op then remove the term "n" is pointing at
264 if (n -> term -> value == LW_OPER_NEG)
265 {
266 n -> prev -> term -> value = -(n -> prev -> term -> value);
267 }
268 else if (n -> term -> value == LW_OPER_COM)
269 {
270 n -> prev -> term -> value = ~(n -> prev -> term -> value);
271 }
272 n -> prev -> next = n -> next;
273 if (n -> next)
274 n -> next -> prev = n -> prev;
275 else
276 s -> tail = n -> prev;
277
278 lw_expr_term_free(n -> term);
279 lw_free(n);
280 break;
281 }
282 }
283 else
284 {
285 // binary operator
286 if (n -> prev && n -> prev -> prev && n -> prev -> term -> term_type == LW_TERM_INT && n -> prev -> prev -> term -> term_type == LW_TERM_INT)
287 {
288 // a binary operator we can resolve
289 switch (n -> term -> value)
290 {
291 case LW_OPER_PLUS:
292 n -> prev -> prev -> term -> value += n -> prev -> term -> value;
293 break;
294
295 case LW_OPER_MINUS:
296 n -> prev -> prev -> term -> value -= n -> prev -> term -> value;
297 break;
298
299 case LW_OPER_TIMES:
300 n -> prev -> prev -> term -> value *= n -> prev -> term -> value;
301 break;
302
303 case LW_OPER_DIVIDE:
304 if (n -> prev -> term -> value == 0)
305 return -1;
306 n -> prev -> prev -> term -> value /= n -> prev -> term -> value;
307 break;
308
309 case LW_OPER_MOD:
310 if (n -> prev -> term -> value == 0)
311 return -1;
312 n -> prev -> prev -> term -> value %= n -> prev -> term -> value;
313 break;
314
315 case LW_OPER_INTDIV:
316 if (n -> prev -> term -> value == 0)
317 return -1;
318 n -> prev -> prev -> term -> value /= n -> prev -> term -> value;
319 break;
320
321 case LW_OPER_BWAND:
322 n -> prev -> prev -> term -> value &= n -> prev -> term -> value;
323 break;
324
325 case LW_OPER_BWOR:
326 n -> prev -> prev -> term -> value |= n -> prev -> term -> value;
327 break;
328
329 case LW_OPER_BWXOR:
330 n -> prev -> prev -> term -> value ^= n -> prev -> term -> value;
331 break;
332
333 case LW_OPER_AND:
334 n -> prev -> prev -> term -> value = (n -> prev -> term -> value && n -> prev -> prev -> term -> value) ? 1 : 0;
335 break;
336
337 case LW_OPER_OR:
338 n -> prev -> prev -> term -> value = (n -> prev -> term -> value || n -> prev -> prev -> term -> value) ? 1 : 0;
339 break;
340
341 default:
342 // return error if unknown operator!
343 return -1;
344 }
345
346 // now remove the two unneeded entries from the stack
347 n -> prev -> prev -> next = n -> next;
348 if (n -> next)
349 n -> next -> prev = n -> prev -> prev;
350 else
351 s -> tail = n -> prev -> prev;
352
353 lw_expr_term_free(n -> term);
354 lw_expr_term_free(n -> prev -> term);
355 lw_free(n -> prev);
356 lw_free(n);
357 break;
358 }
359 }
360 }
361 }
362 // note for the terminally confused about dynamic memory and pointers:
363 // n will not be NULL even after the lw_free calls above so
364 // this test will still work (n will be a dangling pointer)
365 // (n will only be NULL if we didn't find any operators to simplify)
366 if (n)
367 goto next_iter;
368
369 return 0;
370 }