Mercurial > hg-old > index.cgi

comparison lwlink/expr.c @ 139:106c2fe3c9d9

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