Mercurial > hg-old > index.cgi
annotate lwlink/expr.c @ 211:51511cf1c9f8
Prepare for gnulib integration
| author | lost |
|---|---|
| date | Fri, 24 Apr 2009 06:27:00 +0000 |
| parents | 299c5d793aca |
| children | bae1e3ecdce1 |
| 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__ | |
| 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 | |
|
206
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
56 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
|
57 { |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
58 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
|
59 lw_expr_stack_t *s2; |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
60 |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
61 s2 = lw_expr_stack_create(); |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
62 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
|
63 { |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
64 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
|
65 } |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
66 return s2; |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
67 } |
|
299c5d793aca
Made lwlink smarter about not included unneeded (unreferenced) members of a library file
lost
parents:
139
diff
changeset
|
68 |
| 116 | 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 } |