Mercurial > hg-old > index.cgi
annotate lwlink/expr.c @ 263:16c73b13ee0b 2.6 2.6
Branched for 2.6 release
| author | lost |
|---|---|
| date | Tue, 22 Dec 2009 05:25:53 +0000 |
| parents | bae1e3ecdce1 |
| children |
| rev | line source |
|---|---|
| 116 | 1 /* |
| 2 expr.c | |
| 118 | 3 Copyright © 2009 William Astle |
| 116 | 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__ | |
| 212 | 26 #include <config.h> |
| 116 | 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 | |
|
206
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
57 lw_expr_stack_t *lw_expr_stack_dup(lw_expr_stack_t *s) |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
58 { |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
59 lw_expr_stack_node_t *t; |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
60 lw_expr_stack_t *s2; |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
61 |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
62 s2 = lw_expr_stack_create(); |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
63 for (t = s -> head; t; t = t -> next) |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
64 { |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
65 lw_expr_stack_push(s2, t -> term); |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
66 } |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
67 return s2; |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
68 } |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
69 |
| 116 | 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 } |