Mercurial > hg > index.cgi

comparison lwlink/expr.c @ 0:2c24602be78f

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