ia64/linux-2.6.18-xen.hg

view scripts/kconfig/expr.c @ 897:329ea0ccb344

balloon: try harder to balloon up under memory pressure.

Currently if the balloon driver is unable to increase the guest's
reservation it assumes the failure was due to reaching its full
allocation, gives up on the ballooning operation and records the limit
it reached as the "hard limit". The driver will not try again until
the target is set again (even to the same value).

However it is possible that ballooning has in fact failed due to
memory pressure in the host and therefore it is desirable to keep
attempting to reach the target in case memory becomes available. The
most likely scenario is that some guests are ballooning down while
others are ballooning up and therefore there is temporary memory
pressure while things stabilise. You would not expect a well behaved
toolstack to ask a domain to balloon to more than its allocation nor
would you expect it to deliberately over-commit memory by setting
balloon targets which exceed the total host memory.

This patch drops the concept of a hard limit and causes the balloon
driver to retry increasing the reservation on a timer in the same
manner as when decreasing the reservation.

Also if we partially succeed in increasing the reservation
(i.e. receive less pages than we asked for) then we may as well keep
those pages rather than returning them to Xen.

Signed-off-by: Ian Campbell <ian.campbell@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Fri Jun 05 14:01:20 2009 +0100 (2009-06-05)
parents 831230e53067
children
line source
1 /*
2 * Copyright (C) 2002 Roman Zippel <zippel@linux-m68k.org>
3 * Released under the terms of the GNU GPL v2.0.
4 */
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
10 #define LKC_DIRECT_LINK
11 #include "lkc.h"
13 #define DEBUG_EXPR 0
15 struct expr *expr_alloc_symbol(struct symbol *sym)
16 {
17 struct expr *e = malloc(sizeof(*e));
18 memset(e, 0, sizeof(*e));
19 e->type = E_SYMBOL;
20 e->left.sym = sym;
21 return e;
22 }
24 struct expr *expr_alloc_one(enum expr_type type, struct expr *ce)
25 {
26 struct expr *e = malloc(sizeof(*e));
27 memset(e, 0, sizeof(*e));
28 e->type = type;
29 e->left.expr = ce;
30 return e;
31 }
33 struct expr *expr_alloc_two(enum expr_type type, struct expr *e1, struct expr *e2)
34 {
35 struct expr *e = malloc(sizeof(*e));
36 memset(e, 0, sizeof(*e));
37 e->type = type;
38 e->left.expr = e1;
39 e->right.expr = e2;
40 return e;
41 }
43 struct expr *expr_alloc_comp(enum expr_type type, struct symbol *s1, struct symbol *s2)
44 {
45 struct expr *e = malloc(sizeof(*e));
46 memset(e, 0, sizeof(*e));
47 e->type = type;
48 e->left.sym = s1;
49 e->right.sym = s2;
50 return e;
51 }
53 struct expr *expr_alloc_and(struct expr *e1, struct expr *e2)
54 {
55 if (!e1)
56 return e2;
57 return e2 ? expr_alloc_two(E_AND, e1, e2) : e1;
58 }
60 struct expr *expr_alloc_or(struct expr *e1, struct expr *e2)
61 {
62 if (!e1)
63 return e2;
64 return e2 ? expr_alloc_two(E_OR, e1, e2) : e1;
65 }
67 struct expr *expr_copy(struct expr *org)
68 {
69 struct expr *e;
71 if (!org)
72 return NULL;
74 e = malloc(sizeof(*org));
75 memcpy(e, org, sizeof(*org));
76 switch (org->type) {
77 case E_SYMBOL:
78 e->left = org->left;
79 break;
80 case E_NOT:
81 e->left.expr = expr_copy(org->left.expr);
82 break;
83 case E_EQUAL:
84 case E_UNEQUAL:
85 e->left.sym = org->left.sym;
86 e->right.sym = org->right.sym;
87 break;
88 case E_AND:
89 case E_OR:
90 case E_CHOICE:
91 e->left.expr = expr_copy(org->left.expr);
92 e->right.expr = expr_copy(org->right.expr);
93 break;
94 default:
95 printf("can't copy type %d\n", e->type);
96 free(e);
97 e = NULL;
98 break;
99 }
101 return e;
102 }
104 void expr_free(struct expr *e)
105 {
106 if (!e)
107 return;
109 switch (e->type) {
110 case E_SYMBOL:
111 break;
112 case E_NOT:
113 expr_free(e->left.expr);
114 return;
115 case E_EQUAL:
116 case E_UNEQUAL:
117 break;
118 case E_OR:
119 case E_AND:
120 expr_free(e->left.expr);
121 expr_free(e->right.expr);
122 break;
123 default:
124 printf("how to free type %d?\n", e->type);
125 break;
126 }
127 free(e);
128 }
130 static int trans_count;
132 #define e1 (*ep1)
133 #define e2 (*ep2)
135 static void __expr_eliminate_eq(enum expr_type type, struct expr **ep1, struct expr **ep2)
136 {
137 if (e1->type == type) {
138 __expr_eliminate_eq(type, &e1->left.expr, &e2);
139 __expr_eliminate_eq(type, &e1->right.expr, &e2);
140 return;
141 }
142 if (e2->type == type) {
143 __expr_eliminate_eq(type, &e1, &e2->left.expr);
144 __expr_eliminate_eq(type, &e1, &e2->right.expr);
145 return;
146 }
147 if (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
148 e1->left.sym == e2->left.sym &&
149 (e1->left.sym == &symbol_yes || e1->left.sym == &symbol_no))
150 return;
151 if (!expr_eq(e1, e2))
152 return;
153 trans_count++;
154 expr_free(e1); expr_free(e2);
155 switch (type) {
156 case E_OR:
157 e1 = expr_alloc_symbol(&symbol_no);
158 e2 = expr_alloc_symbol(&symbol_no);
159 break;
160 case E_AND:
161 e1 = expr_alloc_symbol(&symbol_yes);
162 e2 = expr_alloc_symbol(&symbol_yes);
163 break;
164 default:
165 ;
166 }
167 }
169 void expr_eliminate_eq(struct expr **ep1, struct expr **ep2)
170 {
171 if (!e1 || !e2)
172 return;
173 switch (e1->type) {
174 case E_OR:
175 case E_AND:
176 __expr_eliminate_eq(e1->type, ep1, ep2);
177 default:
178 ;
179 }
180 if (e1->type != e2->type) switch (e2->type) {
181 case E_OR:
182 case E_AND:
183 __expr_eliminate_eq(e2->type, ep1, ep2);
184 default:
185 ;
186 }
187 e1 = expr_eliminate_yn(e1);
188 e2 = expr_eliminate_yn(e2);
189 }
191 #undef e1
192 #undef e2
194 int expr_eq(struct expr *e1, struct expr *e2)
195 {
196 int res, old_count;
198 if (e1->type != e2->type)
199 return 0;
200 switch (e1->type) {
201 case E_EQUAL:
202 case E_UNEQUAL:
203 return e1->left.sym == e2->left.sym && e1->right.sym == e2->right.sym;
204 case E_SYMBOL:
205 return e1->left.sym == e2->left.sym;
206 case E_NOT:
207 return expr_eq(e1->left.expr, e2->left.expr);
208 case E_AND:
209 case E_OR:
210 e1 = expr_copy(e1);
211 e2 = expr_copy(e2);
212 old_count = trans_count;
213 expr_eliminate_eq(&e1, &e2);
214 res = (e1->type == E_SYMBOL && e2->type == E_SYMBOL &&
215 e1->left.sym == e2->left.sym);
216 expr_free(e1);
217 expr_free(e2);
218 trans_count = old_count;
219 return res;
220 case E_CHOICE:
221 case E_RANGE:
222 case E_NONE:
223 /* panic */;
224 }
226 if (DEBUG_EXPR) {
227 expr_fprint(e1, stdout);
228 printf(" = ");
229 expr_fprint(e2, stdout);
230 printf(" ?\n");
231 }
233 return 0;
234 }
236 struct expr *expr_eliminate_yn(struct expr *e)
237 {
238 struct expr *tmp;
240 if (e) switch (e->type) {
241 case E_AND:
242 e->left.expr = expr_eliminate_yn(e->left.expr);
243 e->right.expr = expr_eliminate_yn(e->right.expr);
244 if (e->left.expr->type == E_SYMBOL) {
245 if (e->left.expr->left.sym == &symbol_no) {
246 expr_free(e->left.expr);
247 expr_free(e->right.expr);
248 e->type = E_SYMBOL;
249 e->left.sym = &symbol_no;
250 e->right.expr = NULL;
251 return e;
252 } else if (e->left.expr->left.sym == &symbol_yes) {
253 free(e->left.expr);
254 tmp = e->right.expr;
255 *e = *(e->right.expr);
256 free(tmp);
257 return e;
258 }
259 }
260 if (e->right.expr->type == E_SYMBOL) {
261 if (e->right.expr->left.sym == &symbol_no) {
262 expr_free(e->left.expr);
263 expr_free(e->right.expr);
264 e->type = E_SYMBOL;
265 e->left.sym = &symbol_no;
266 e->right.expr = NULL;
267 return e;
268 } else if (e->right.expr->left.sym == &symbol_yes) {
269 free(e->right.expr);
270 tmp = e->left.expr;
271 *e = *(e->left.expr);
272 free(tmp);
273 return e;
274 }
275 }
276 break;
277 case E_OR:
278 e->left.expr = expr_eliminate_yn(e->left.expr);
279 e->right.expr = expr_eliminate_yn(e->right.expr);
280 if (e->left.expr->type == E_SYMBOL) {
281 if (e->left.expr->left.sym == &symbol_no) {
282 free(e->left.expr);
283 tmp = e->right.expr;
284 *e = *(e->right.expr);
285 free(tmp);
286 return e;
287 } else if (e->left.expr->left.sym == &symbol_yes) {
288 expr_free(e->left.expr);
289 expr_free(e->right.expr);
290 e->type = E_SYMBOL;
291 e->left.sym = &symbol_yes;
292 e->right.expr = NULL;
293 return e;
294 }
295 }
296 if (e->right.expr->type == E_SYMBOL) {
297 if (e->right.expr->left.sym == &symbol_no) {
298 free(e->right.expr);
299 tmp = e->left.expr;
300 *e = *(e->left.expr);
301 free(tmp);
302 return e;
303 } else if (e->right.expr->left.sym == &symbol_yes) {
304 expr_free(e->left.expr);
305 expr_free(e->right.expr);
306 e->type = E_SYMBOL;
307 e->left.sym = &symbol_yes;
308 e->right.expr = NULL;
309 return e;
310 }
311 }
312 break;
313 default:
314 ;
315 }
316 return e;
317 }
319 /*
320 * bool FOO!=n => FOO
321 */
322 struct expr *expr_trans_bool(struct expr *e)
323 {
324 if (!e)
325 return NULL;
326 switch (e->type) {
327 case E_AND:
328 case E_OR:
329 case E_NOT:
330 e->left.expr = expr_trans_bool(e->left.expr);
331 e->right.expr = expr_trans_bool(e->right.expr);
332 break;
333 case E_UNEQUAL:
334 // FOO!=n -> FOO
335 if (e->left.sym->type == S_TRISTATE) {
336 if (e->right.sym == &symbol_no) {
337 e->type = E_SYMBOL;
338 e->right.sym = NULL;
339 }
340 }
341 break;
342 default:
343 ;
344 }
345 return e;
346 }
348 /*
349 * e1 || e2 -> ?
350 */
351 struct expr *expr_join_or(struct expr *e1, struct expr *e2)
352 {
353 struct expr *tmp;
354 struct symbol *sym1, *sym2;
356 if (expr_eq(e1, e2))
357 return expr_copy(e1);
358 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
359 return NULL;
360 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
361 return NULL;
362 if (e1->type == E_NOT) {
363 tmp = e1->left.expr;
364 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
365 return NULL;
366 sym1 = tmp->left.sym;
367 } else
368 sym1 = e1->left.sym;
369 if (e2->type == E_NOT) {
370 if (e2->left.expr->type != E_SYMBOL)
371 return NULL;
372 sym2 = e2->left.expr->left.sym;
373 } else
374 sym2 = e2->left.sym;
375 if (sym1 != sym2)
376 return NULL;
377 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
378 return NULL;
379 if (sym1->type == S_TRISTATE) {
380 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
381 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
382 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes))) {
383 // (a='y') || (a='m') -> (a!='n')
384 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_no);
385 }
386 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
387 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
388 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes))) {
389 // (a='y') || (a='n') -> (a!='m')
390 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_mod);
391 }
392 if (e1->type == E_EQUAL && e2->type == E_EQUAL &&
393 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
394 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod))) {
395 // (a='m') || (a='n') -> (a!='y')
396 return expr_alloc_comp(E_UNEQUAL, sym1, &symbol_yes);
397 }
398 }
399 if (sym1->type == S_BOOLEAN && sym1 == sym2) {
400 if ((e1->type == E_NOT && e1->left.expr->type == E_SYMBOL && e2->type == E_SYMBOL) ||
401 (e2->type == E_NOT && e2->left.expr->type == E_SYMBOL && e1->type == E_SYMBOL))
402 return expr_alloc_symbol(&symbol_yes);
403 }
405 if (DEBUG_EXPR) {
406 printf("optimize (");
407 expr_fprint(e1, stdout);
408 printf(") || (");
409 expr_fprint(e2, stdout);
410 printf(")?\n");
411 }
412 return NULL;
413 }
415 struct expr *expr_join_and(struct expr *e1, struct expr *e2)
416 {
417 struct expr *tmp;
418 struct symbol *sym1, *sym2;
420 if (expr_eq(e1, e2))
421 return expr_copy(e1);
422 if (e1->type != E_EQUAL && e1->type != E_UNEQUAL && e1->type != E_SYMBOL && e1->type != E_NOT)
423 return NULL;
424 if (e2->type != E_EQUAL && e2->type != E_UNEQUAL && e2->type != E_SYMBOL && e2->type != E_NOT)
425 return NULL;
426 if (e1->type == E_NOT) {
427 tmp = e1->left.expr;
428 if (tmp->type != E_EQUAL && tmp->type != E_UNEQUAL && tmp->type != E_SYMBOL)
429 return NULL;
430 sym1 = tmp->left.sym;
431 } else
432 sym1 = e1->left.sym;
433 if (e2->type == E_NOT) {
434 if (e2->left.expr->type != E_SYMBOL)
435 return NULL;
436 sym2 = e2->left.expr->left.sym;
437 } else
438 sym2 = e2->left.sym;
439 if (sym1 != sym2)
440 return NULL;
441 if (sym1->type != S_BOOLEAN && sym1->type != S_TRISTATE)
442 return NULL;
444 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_yes) ||
445 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_yes))
446 // (a) && (a='y') -> (a='y')
447 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
449 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_no) ||
450 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_no))
451 // (a) && (a!='n') -> (a)
452 return expr_alloc_symbol(sym1);
454 if ((e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_mod) ||
455 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_mod))
456 // (a) && (a!='m') -> (a='y')
457 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
459 if (sym1->type == S_TRISTATE) {
460 if (e1->type == E_EQUAL && e2->type == E_UNEQUAL) {
461 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
462 sym2 = e1->right.sym;
463 if ((e2->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
464 return sym2 != e2->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
465 : expr_alloc_symbol(&symbol_no);
466 }
467 if (e1->type == E_UNEQUAL && e2->type == E_EQUAL) {
468 // (a='b') && (a!='c') -> 'b'='c' ? 'n' : a='b'
469 sym2 = e2->right.sym;
470 if ((e1->right.sym->flags & SYMBOL_CONST) && (sym2->flags & SYMBOL_CONST))
471 return sym2 != e1->right.sym ? expr_alloc_comp(E_EQUAL, sym1, sym2)
472 : expr_alloc_symbol(&symbol_no);
473 }
474 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
475 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_no) ||
476 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_yes)))
477 // (a!='y') && (a!='n') -> (a='m')
478 return expr_alloc_comp(E_EQUAL, sym1, &symbol_mod);
480 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
481 ((e1->right.sym == &symbol_yes && e2->right.sym == &symbol_mod) ||
482 (e1->right.sym == &symbol_mod && e2->right.sym == &symbol_yes)))
483 // (a!='y') && (a!='m') -> (a='n')
484 return expr_alloc_comp(E_EQUAL, sym1, &symbol_no);
486 if (e1->type == E_UNEQUAL && e2->type == E_UNEQUAL &&
487 ((e1->right.sym == &symbol_mod && e2->right.sym == &symbol_no) ||
488 (e1->right.sym == &symbol_no && e2->right.sym == &symbol_mod)))
489 // (a!='m') && (a!='n') -> (a='m')
490 return expr_alloc_comp(E_EQUAL, sym1, &symbol_yes);
492 if ((e1->type == E_SYMBOL && e2->type == E_EQUAL && e2->right.sym == &symbol_mod) ||
493 (e2->type == E_SYMBOL && e1->type == E_EQUAL && e1->right.sym == &symbol_mod) ||
494 (e1->type == E_SYMBOL && e2->type == E_UNEQUAL && e2->right.sym == &symbol_yes) ||
495 (e2->type == E_SYMBOL && e1->type == E_UNEQUAL && e1->right.sym == &symbol_yes))
496 return NULL;
497 }
499 if (DEBUG_EXPR) {
500 printf("optimize (");
501 expr_fprint(e1, stdout);
502 printf(") && (");
503 expr_fprint(e2, stdout);
504 printf(")?\n");
505 }
506 return NULL;
507 }
509 static void expr_eliminate_dups1(enum expr_type type, struct expr **ep1, struct expr **ep2)
510 {
511 #define e1 (*ep1)
512 #define e2 (*ep2)
513 struct expr *tmp;
515 if (e1->type == type) {
516 expr_eliminate_dups1(type, &e1->left.expr, &e2);
517 expr_eliminate_dups1(type, &e1->right.expr, &e2);
518 return;
519 }
520 if (e2->type == type) {
521 expr_eliminate_dups1(type, &e1, &e2->left.expr);
522 expr_eliminate_dups1(type, &e1, &e2->right.expr);
523 return;
524 }
525 if (e1 == e2)
526 return;
528 switch (e1->type) {
529 case E_OR: case E_AND:
530 expr_eliminate_dups1(e1->type, &e1, &e1);
531 default:
532 ;
533 }
535 switch (type) {
536 case E_OR:
537 tmp = expr_join_or(e1, e2);
538 if (tmp) {
539 expr_free(e1); expr_free(e2);
540 e1 = expr_alloc_symbol(&symbol_no);
541 e2 = tmp;
542 trans_count++;
543 }
544 break;
545 case E_AND:
546 tmp = expr_join_and(e1, e2);
547 if (tmp) {
548 expr_free(e1); expr_free(e2);
549 e1 = expr_alloc_symbol(&symbol_yes);
550 e2 = tmp;
551 trans_count++;
552 }
553 break;
554 default:
555 ;
556 }
557 #undef e1
558 #undef e2
559 }
561 static void expr_eliminate_dups2(enum expr_type type, struct expr **ep1, struct expr **ep2)
562 {
563 #define e1 (*ep1)
564 #define e2 (*ep2)
565 struct expr *tmp, *tmp1, *tmp2;
567 if (e1->type == type) {
568 expr_eliminate_dups2(type, &e1->left.expr, &e2);
569 expr_eliminate_dups2(type, &e1->right.expr, &e2);
570 return;
571 }
572 if (e2->type == type) {
573 expr_eliminate_dups2(type, &e1, &e2->left.expr);
574 expr_eliminate_dups2(type, &e1, &e2->right.expr);
575 }
576 if (e1 == e2)
577 return;
579 switch (e1->type) {
580 case E_OR:
581 expr_eliminate_dups2(e1->type, &e1, &e1);
582 // (FOO || BAR) && (!FOO && !BAR) -> n
583 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
584 tmp2 = expr_copy(e2);
585 tmp = expr_extract_eq_and(&tmp1, &tmp2);
586 if (expr_is_yes(tmp1)) {
587 expr_free(e1);
588 e1 = expr_alloc_symbol(&symbol_no);
589 trans_count++;
590 }
591 expr_free(tmp2);
592 expr_free(tmp1);
593 expr_free(tmp);
594 break;
595 case E_AND:
596 expr_eliminate_dups2(e1->type, &e1, &e1);
597 // (FOO && BAR) || (!FOO || !BAR) -> y
598 tmp1 = expr_transform(expr_alloc_one(E_NOT, expr_copy(e1)));
599 tmp2 = expr_copy(e2);
600 tmp = expr_extract_eq_or(&tmp1, &tmp2);
601 if (expr_is_no(tmp1)) {
602 expr_free(e1);
603 e1 = expr_alloc_symbol(&symbol_yes);
604 trans_count++;
605 }
606 expr_free(tmp2);
607 expr_free(tmp1);
608 expr_free(tmp);
609 break;
610 default:
611 ;
612 }
613 #undef e1
614 #undef e2
615 }
617 struct expr *expr_eliminate_dups(struct expr *e)
618 {
619 int oldcount;
620 if (!e)
621 return e;
623 oldcount = trans_count;
624 while (1) {
625 trans_count = 0;
626 switch (e->type) {
627 case E_OR: case E_AND:
628 expr_eliminate_dups1(e->type, &e, &e);
629 expr_eliminate_dups2(e->type, &e, &e);
630 default:
631 ;
632 }
633 if (!trans_count)
634 break;
635 e = expr_eliminate_yn(e);
636 }
637 trans_count = oldcount;
638 return e;
639 }
641 struct expr *expr_transform(struct expr *e)
642 {
643 struct expr *tmp;
645 if (!e)
646 return NULL;
647 switch (e->type) {
648 case E_EQUAL:
649 case E_UNEQUAL:
650 case E_SYMBOL:
651 case E_CHOICE:
652 break;
653 default:
654 e->left.expr = expr_transform(e->left.expr);
655 e->right.expr = expr_transform(e->right.expr);
656 }
658 switch (e->type) {
659 case E_EQUAL:
660 if (e->left.sym->type != S_BOOLEAN)
661 break;
662 if (e->right.sym == &symbol_no) {
663 e->type = E_NOT;
664 e->left.expr = expr_alloc_symbol(e->left.sym);
665 e->right.sym = NULL;
666 break;
667 }
668 if (e->right.sym == &symbol_mod) {
669 printf("boolean symbol %s tested for 'm'? test forced to 'n'\n", e->left.sym->name);
670 e->type = E_SYMBOL;
671 e->left.sym = &symbol_no;
672 e->right.sym = NULL;
673 break;
674 }
675 if (e->right.sym == &symbol_yes) {
676 e->type = E_SYMBOL;
677 e->right.sym = NULL;
678 break;
679 }
680 break;
681 case E_UNEQUAL:
682 if (e->left.sym->type != S_BOOLEAN)
683 break;
684 if (e->right.sym == &symbol_no) {
685 e->type = E_SYMBOL;
686 e->right.sym = NULL;
687 break;
688 }
689 if (e->right.sym == &symbol_mod) {
690 printf("boolean symbol %s tested for 'm'? test forced to 'y'\n", e->left.sym->name);
691 e->type = E_SYMBOL;
692 e->left.sym = &symbol_yes;
693 e->right.sym = NULL;
694 break;
695 }
696 if (e->right.sym == &symbol_yes) {
697 e->type = E_NOT;
698 e->left.expr = expr_alloc_symbol(e->left.sym);
699 e->right.sym = NULL;
700 break;
701 }
702 break;
703 case E_NOT:
704 switch (e->left.expr->type) {
705 case E_NOT:
706 // !!a -> a
707 tmp = e->left.expr->left.expr;
708 free(e->left.expr);
709 free(e);
710 e = tmp;
711 e = expr_transform(e);
712 break;
713 case E_EQUAL:
714 case E_UNEQUAL:
715 // !a='x' -> a!='x'
716 tmp = e->left.expr;
717 free(e);
718 e = tmp;
719 e->type = e->type == E_EQUAL ? E_UNEQUAL : E_EQUAL;
720 break;
721 case E_OR:
722 // !(a || b) -> !a && !b
723 tmp = e->left.expr;
724 e->type = E_AND;
725 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
726 tmp->type = E_NOT;
727 tmp->right.expr = NULL;
728 e = expr_transform(e);
729 break;
730 case E_AND:
731 // !(a && b) -> !a || !b
732 tmp = e->left.expr;
733 e->type = E_OR;
734 e->right.expr = expr_alloc_one(E_NOT, tmp->right.expr);
735 tmp->type = E_NOT;
736 tmp->right.expr = NULL;
737 e = expr_transform(e);
738 break;
739 case E_SYMBOL:
740 if (e->left.expr->left.sym == &symbol_yes) {
741 // !'y' -> 'n'
742 tmp = e->left.expr;
743 free(e);
744 e = tmp;
745 e->type = E_SYMBOL;
746 e->left.sym = &symbol_no;
747 break;
748 }
749 if (e->left.expr->left.sym == &symbol_mod) {
750 // !'m' -> 'm'
751 tmp = e->left.expr;
752 free(e);
753 e = tmp;
754 e->type = E_SYMBOL;
755 e->left.sym = &symbol_mod;
756 break;
757 }
758 if (e->left.expr->left.sym == &symbol_no) {
759 // !'n' -> 'y'
760 tmp = e->left.expr;
761 free(e);
762 e = tmp;
763 e->type = E_SYMBOL;
764 e->left.sym = &symbol_yes;
765 break;
766 }
767 break;
768 default:
769 ;
770 }
771 break;
772 default:
773 ;
774 }
775 return e;
776 }
778 int expr_contains_symbol(struct expr *dep, struct symbol *sym)
779 {
780 if (!dep)
781 return 0;
783 switch (dep->type) {
784 case E_AND:
785 case E_OR:
786 return expr_contains_symbol(dep->left.expr, sym) ||
787 expr_contains_symbol(dep->right.expr, sym);
788 case E_SYMBOL:
789 return dep->left.sym == sym;
790 case E_EQUAL:
791 case E_UNEQUAL:
792 return dep->left.sym == sym ||
793 dep->right.sym == sym;
794 case E_NOT:
795 return expr_contains_symbol(dep->left.expr, sym);
796 default:
797 ;
798 }
799 return 0;
800 }
802 bool expr_depends_symbol(struct expr *dep, struct symbol *sym)
803 {
804 if (!dep)
805 return false;
807 switch (dep->type) {
808 case E_AND:
809 return expr_depends_symbol(dep->left.expr, sym) ||
810 expr_depends_symbol(dep->right.expr, sym);
811 case E_SYMBOL:
812 return dep->left.sym == sym;
813 case E_EQUAL:
814 if (dep->left.sym == sym) {
815 if (dep->right.sym == &symbol_yes || dep->right.sym == &symbol_mod)
816 return true;
817 }
818 break;
819 case E_UNEQUAL:
820 if (dep->left.sym == sym) {
821 if (dep->right.sym == &symbol_no)
822 return true;
823 }
824 break;
825 default:
826 ;
827 }
828 return false;
829 }
831 struct expr *expr_extract_eq_and(struct expr **ep1, struct expr **ep2)
832 {
833 struct expr *tmp = NULL;
834 expr_extract_eq(E_AND, &tmp, ep1, ep2);
835 if (tmp) {
836 *ep1 = expr_eliminate_yn(*ep1);
837 *ep2 = expr_eliminate_yn(*ep2);
838 }
839 return tmp;
840 }
842 struct expr *expr_extract_eq_or(struct expr **ep1, struct expr **ep2)
843 {
844 struct expr *tmp = NULL;
845 expr_extract_eq(E_OR, &tmp, ep1, ep2);
846 if (tmp) {
847 *ep1 = expr_eliminate_yn(*ep1);
848 *ep2 = expr_eliminate_yn(*ep2);
849 }
850 return tmp;
851 }
853 void expr_extract_eq(enum expr_type type, struct expr **ep, struct expr **ep1, struct expr **ep2)
854 {
855 #define e1 (*ep1)
856 #define e2 (*ep2)
857 if (e1->type == type) {
858 expr_extract_eq(type, ep, &e1->left.expr, &e2);
859 expr_extract_eq(type, ep, &e1->right.expr, &e2);
860 return;
861 }
862 if (e2->type == type) {
863 expr_extract_eq(type, ep, ep1, &e2->left.expr);
864 expr_extract_eq(type, ep, ep1, &e2->right.expr);
865 return;
866 }
867 if (expr_eq(e1, e2)) {
868 *ep = *ep ? expr_alloc_two(type, *ep, e1) : e1;
869 expr_free(e2);
870 if (type == E_AND) {
871 e1 = expr_alloc_symbol(&symbol_yes);
872 e2 = expr_alloc_symbol(&symbol_yes);
873 } else if (type == E_OR) {
874 e1 = expr_alloc_symbol(&symbol_no);
875 e2 = expr_alloc_symbol(&symbol_no);
876 }
877 }
878 #undef e1
879 #undef e2
880 }
882 struct expr *expr_trans_compare(struct expr *e, enum expr_type type, struct symbol *sym)
883 {
884 struct expr *e1, *e2;
886 if (!e) {
887 e = expr_alloc_symbol(sym);
888 if (type == E_UNEQUAL)
889 e = expr_alloc_one(E_NOT, e);
890 return e;
891 }
892 switch (e->type) {
893 case E_AND:
894 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
895 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
896 if (sym == &symbol_yes)
897 e = expr_alloc_two(E_AND, e1, e2);
898 if (sym == &symbol_no)
899 e = expr_alloc_two(E_OR, e1, e2);
900 if (type == E_UNEQUAL)
901 e = expr_alloc_one(E_NOT, e);
902 return e;
903 case E_OR:
904 e1 = expr_trans_compare(e->left.expr, E_EQUAL, sym);
905 e2 = expr_trans_compare(e->right.expr, E_EQUAL, sym);
906 if (sym == &symbol_yes)
907 e = expr_alloc_two(E_OR, e1, e2);
908 if (sym == &symbol_no)
909 e = expr_alloc_two(E_AND, e1, e2);
910 if (type == E_UNEQUAL)
911 e = expr_alloc_one(E_NOT, e);
912 return e;
913 case E_NOT:
914 return expr_trans_compare(e->left.expr, type == E_EQUAL ? E_UNEQUAL : E_EQUAL, sym);
915 case E_UNEQUAL:
916 case E_EQUAL:
917 if (type == E_EQUAL) {
918 if (sym == &symbol_yes)
919 return expr_copy(e);
920 if (sym == &symbol_mod)
921 return expr_alloc_symbol(&symbol_no);
922 if (sym == &symbol_no)
923 return expr_alloc_one(E_NOT, expr_copy(e));
924 } else {
925 if (sym == &symbol_yes)
926 return expr_alloc_one(E_NOT, expr_copy(e));
927 if (sym == &symbol_mod)
928 return expr_alloc_symbol(&symbol_yes);
929 if (sym == &symbol_no)
930 return expr_copy(e);
931 }
932 break;
933 case E_SYMBOL:
934 return expr_alloc_comp(type, e->left.sym, sym);
935 case E_CHOICE:
936 case E_RANGE:
937 case E_NONE:
938 /* panic */;
939 }
940 return NULL;
941 }
943 tristate expr_calc_value(struct expr *e)
944 {
945 tristate val1, val2;
946 const char *str1, *str2;
948 if (!e)
949 return yes;
951 switch (e->type) {
952 case E_SYMBOL:
953 sym_calc_value(e->left.sym);
954 return e->left.sym->curr.tri;
955 case E_AND:
956 val1 = expr_calc_value(e->left.expr);
957 val2 = expr_calc_value(e->right.expr);
958 return E_AND(val1, val2);
959 case E_OR:
960 val1 = expr_calc_value(e->left.expr);
961 val2 = expr_calc_value(e->right.expr);
962 return E_OR(val1, val2);
963 case E_NOT:
964 val1 = expr_calc_value(e->left.expr);
965 return E_NOT(val1);
966 case E_EQUAL:
967 sym_calc_value(e->left.sym);
968 sym_calc_value(e->right.sym);
969 str1 = sym_get_string_value(e->left.sym);
970 str2 = sym_get_string_value(e->right.sym);
971 return !strcmp(str1, str2) ? yes : no;
972 case E_UNEQUAL:
973 sym_calc_value(e->left.sym);
974 sym_calc_value(e->right.sym);
975 str1 = sym_get_string_value(e->left.sym);
976 str2 = sym_get_string_value(e->right.sym);
977 return !strcmp(str1, str2) ? no : yes;
978 default:
979 printf("expr_calc_value: %d?\n", e->type);
980 return no;
981 }
982 }
984 int expr_compare_type(enum expr_type t1, enum expr_type t2)
985 {
986 #if 0
987 return 1;
988 #else
989 if (t1 == t2)
990 return 0;
991 switch (t1) {
992 case E_EQUAL:
993 case E_UNEQUAL:
994 if (t2 == E_NOT)
995 return 1;
996 case E_NOT:
997 if (t2 == E_AND)
998 return 1;
999 case E_AND:
1000 if (t2 == E_OR)
1001 return 1;
1002 case E_OR:
1003 if (t2 == E_CHOICE)
1004 return 1;
1005 case E_CHOICE:
1006 if (t2 == 0)
1007 return 1;
1008 default:
1009 return -1;
1011 printf("[%dgt%d?]", t1, t2);
1012 return 0;
1013 #endif
1016 void expr_print(struct expr *e, void (*fn)(void *, struct symbol *, const char *), void *data, int prevtoken)
1018 if (!e) {
1019 fn(data, NULL, "y");
1020 return;
1023 if (expr_compare_type(prevtoken, e->type) > 0)
1024 fn(data, NULL, "(");
1025 switch (e->type) {
1026 case E_SYMBOL:
1027 if (e->left.sym->name)
1028 fn(data, e->left.sym, e->left.sym->name);
1029 else
1030 fn(data, NULL, "<choice>");
1031 break;
1032 case E_NOT:
1033 fn(data, NULL, "!");
1034 expr_print(e->left.expr, fn, data, E_NOT);
1035 break;
1036 case E_EQUAL:
1037 fn(data, e->left.sym, e->left.sym->name);
1038 fn(data, NULL, "=");
1039 fn(data, e->right.sym, e->right.sym->name);
1040 break;
1041 case E_UNEQUAL:
1042 fn(data, e->left.sym, e->left.sym->name);
1043 fn(data, NULL, "!=");
1044 fn(data, e->right.sym, e->right.sym->name);
1045 break;
1046 case E_OR:
1047 expr_print(e->left.expr, fn, data, E_OR);
1048 fn(data, NULL, " || ");
1049 expr_print(e->right.expr, fn, data, E_OR);
1050 break;
1051 case E_AND:
1052 expr_print(e->left.expr, fn, data, E_AND);
1053 fn(data, NULL, " && ");
1054 expr_print(e->right.expr, fn, data, E_AND);
1055 break;
1056 case E_CHOICE:
1057 fn(data, e->right.sym, e->right.sym->name);
1058 if (e->left.expr) {
1059 fn(data, NULL, " ^ ");
1060 expr_print(e->left.expr, fn, data, E_CHOICE);
1062 break;
1063 case E_RANGE:
1064 fn(data, NULL, "[");
1065 fn(data, e->left.sym, e->left.sym->name);
1066 fn(data, NULL, " ");
1067 fn(data, e->right.sym, e->right.sym->name);
1068 fn(data, NULL, "]");
1069 break;
1070 default:
1072 char buf[32];
1073 sprintf(buf, "<unknown type %d>", e->type);
1074 fn(data, NULL, buf);
1075 break;
1078 if (expr_compare_type(prevtoken, e->type) > 0)
1079 fn(data, NULL, ")");
1082 static void expr_print_file_helper(void *data, struct symbol *sym, const char *str)
1084 fwrite(str, strlen(str), 1, data);
1087 void expr_fprint(struct expr *e, FILE *out)
1089 expr_print(e, expr_print_file_helper, out, E_NONE);
1092 static void expr_print_gstr_helper(void *data, struct symbol *sym, const char *str)
1094 str_append((struct gstr*)data, str);
1097 void expr_gstr_print(struct expr *e, struct gstr *gs)
1099 expr_print(e, expr_print_gstr_helper, gs, E_NONE);