/* $Id: evaluator.c,v 1.25 2005/05/08 04:32:44 reinelt Exp $ * * expression evaluation * * Copyright (C) 1999, 2000 Michael Reinelt * Copyright (C) 2004 The LCD4Linux Team * * This file is part of LCD4Linux. * * LCD4Linux is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2, or (at your option) * any later version. * * LCD4Linux is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. * * * $Log: evaluator.c,v $ * Revision 1.25 2005/05/08 04:32:44 reinelt * CodingStyle added and applied * * Revision 1.24 2005/03/30 04:57:50 reinelt * Evaluator speedup: use bsearch for finding functions and variables * * Revision 1.23 2005/01/18 06:30:23 reinelt * added (C) to all copyright statements * * Revision 1.22 2004/06/26 12:04:59 reinelt * * uh-oh... the last CVS log message messed up things a lot... * * Revision 1.21 2004/06/26 09:27:21 reinelt * * added '-W' to CFLAGS * changed all C++ comments to C ones * cleaned up a lot of signed/unsigned mistakes * * Revision 1.20 2004/06/20 10:09:56 reinelt * * 'const'ified the whole source * * Revision 1.19 2004/04/12 11:12:25 reinelt * added plugin_isdn, removed old ISDN client * fixed some real bad bugs in the evaluator * * Revision 1.18 2004/03/11 06:39:58 reinelt * big patch from Martin: * - reuse filehandles * - memory leaks fixed * - earlier busy-flag checking with HD44780 * - reuse memory for strings in RESULT and hash * - netdev_fast to wavid time-consuming regex * * Revision 1.17 2004/03/08 18:45:52 hejl * fixed segfault when using string concatenation * * Revision 1.16 2004/03/08 04:33:08 reinelt * string concatenation fixed * * Revision 1.15 2004/03/06 20:31:16 reinelt * Complete rewrite of the evaluator to get rid of the code * from mark Morley (because of license issues). * The new Evaluator does a pre-compile of expressions, and * stores them in trees. Therefore it should be reasonable faster... * * Revision 1.14 2004/03/03 03:47:04 reinelt * big patch from Martin Hejl: * - use qprintf() where appropriate * - save CPU cycles on gettimeofday() * - add quit() functions to free allocated memory * - fixed lots of memory leaks * * Revision 1.13 2004/02/26 21:42:45 reinelt * memory leak fixes from Martin * * Revision 1.12 2004/02/05 07:10:23 reinelt * evaluator function names are no longer case-sensitive * Crystalfontz Fan PWM control, Fan RPM monitoring, temperature monitoring * * Revision 1.11 2004/01/30 20:57:56 reinelt * HD44780 patch from Martin Hejl * dmalloc integrated * * Revision 1.10 2004/01/29 04:40:02 reinelt * every .c file includes "config.h" now * * Revision 1.9 2004/01/15 07:47:02 reinelt * debian/ postinst and watch added (did CVS forget about them?) * evaluator: conditional expressions (a?b:c) added * text widget nearly finished * * Revision 1.8 2004/01/12 03:51:01 reinelt * evaluating the 'Variables' section in the config file * * Revision 1.7 2004/01/07 10:15:41 reinelt * small glitch in evaluator fixed * made config table sorted and access with bsearch(), * which should be much faster * * Revision 1.6 2004/01/06 23:01:37 reinelt * more copyright issues * * Revision 1.5 2004/01/06 17:33:45 reinelt * Evaluator: functions with variable argument lists * Evaluator: plugin_sample.c and README.Plugins added * * Revision 1.4 2004/01/06 15:19:12 reinelt * Evaluator rearrangeme

# Sweden - Dalfors
# T freq bw fec_hi fec_lo mod transmission-mode guard-interval hierarchy
T 602000000 8MHz 2/3 NONE QAM64 8k 1/8 NONE

if (*result == NULL) { if ((*result = NewResult()) == NULL) return NULL; } else if (type == R_NUMBER) { DelResult(*result); } if (type == R_NUMBER) { (*result)->type = R_NUMBER; (*result)->number = *(double *) value; (*result)->length = -1; (*result)->string = NULL; } else if (type == R_STRING) { int len = strlen((char *) value); (*result)->type = R_STRING; (*result)->number = 0.0; if ((*result)->string == NULL || len > (*result)->length) { /* buffer is either empty or too small */ if ((*result)->string) free((*result)->string); /* allocate memory in multiples of CHUNK_SIZE */ /* note that length does not count the trailing \0 */ (*result)->length = CHUNK_SIZE * (len / CHUNK_SIZE + 1) - 1; (*result)->string = malloc((*result)->length + 1); } strcpy((*result)->string, value); } else { error("Evaluator: internal error: invalid result type %d", type); return NULL; } return *result; } double R2N(RESULT * result) { if (result == NULL) { error("Evaluator: internal error: NULL result"); return 0.0; } if (result->type & R_NUMBER) { return result->number; } if (result->type & R_STRING) { result->type |= R_NUMBER; result->number = atof(result->string); return result->number; } error("Evaluator: internal error: invalid result type %d", result->type); return 0.0; } char *R2S(RESULT * result) { if (result == NULL) { error("Evaluator: internal error: NULL result"); return NULL; } if (result->type & R_STRING) { return result->string; } if (result->type & R_NUMBER) { result->type |= R_STRING; if (result->string) free(result->string); result->length = CHUNK_SIZE - 1; result->string = malloc(CHUNK_SIZE); snprintf(result->string, CHUNK_SIZE, "%g", result->number); return result->string; } error("Evaluator: internal error: invalid result type %d", result->type); return NULL; } /* bsearch compare function for variables */ static int LookupVariable(const void *a, const void *b) { char *key = (char *) a; VARIABLE *var = (VARIABLE *) b; return strcmp(key, var->name); } /* qsort compare function for variables */ static int SortVariable(const void *a, const void *b) { VARIABLE *va = (VARIABLE *) a; VARIABLE *vb = (VARIABLE *) b; return strcmp(va->name, vb->name); } static VARIABLE *FindVariable(const char *name) { return bsearch(name, Variable, nVariable, sizeof(VARIABLE), LookupVariable); } int SetVariable(const char *name, RESULT * value) { VARIABLE *V; V = FindVariable(name); if (V != NULL) { FreeResult(V->value); V->value = DupResult(value); return 1; } nVariable++; Variable = realloc(Variable, nVariable * sizeof(VARIABLE)); Variable[nVariable - 1].name = strdup(name); Variable[nVariable - 1].value = DupResult(value); qsort(Variable, nVariable, sizeof(VARIABLE), SortVariable); return 0; } int SetVariableNumeric(const char *name, const double value) { RESULT result = { 0, 0, 0, NULL }; RESULT *rp = &result; SetResult(&rp, R_NUMBER, &value); return SetVariable(name, rp); } int SetVariableString(const char *name, const char *value) { RESULT result = { 0, 0, 0, NULL }; RESULT *rp = &result; SetResult(&rp, R_STRING, value); return SetVariable(name, rp); } void DeleteVariables(void) { int i; for (i = 0; i < nVariable; i++) { free(Variable[i].name); FreeResult(Variable[i].value); } free(Variable); Variable = NULL; nVariable = 0; } /* bsearch compare function for functions */ static int LookupFunction(const void *a, const void *b) { char *n = (char *) a; FUNCTION *f = (FUNCTION *) b; return strcmp(n, f->name); } /* qsort compare function for functions */ static int SortFunction(const void *a, const void *b) { FUNCTION *fa = (FUNCTION *) a; FUNCTION *fb = (FUNCTION *) b; return strcmp(fa->name, fb->name); } static FUNCTION *FindFunction(const char *name) { return bsearch(name, Function, nFunction, sizeof(FUNCTION), LookupFunction); } int AddFunction(const char *name, const int argc, void (*func) ()) { nFunction++; Function = realloc(Function, nFunction * sizeof(FUNCTION)); Function[nFunction - 1].name = strdup(name); Function[nFunction - 1].argc = argc; Function[nFunction - 1].func = func; qsort(Function, nFunction, sizeof(FUNCTION), SortFunction); return 0; } void DeleteFunctions(void) { int i; for (i = 0; i < nFunction; i++) { free(Function[i].name); } free(Function); Function = NULL; nFunction = 0; } #define is_space(c) ((c) == ' ' || (c) == '\t') #define is_digit(c) ((c) >= '0' && (c) <= '9') #define is_alpha(c) (((c) >= 'A' && (c) <= 'Z') || ((c) >= 'a' && (c) <= 'z') || ((c) == '_')) #define is_alnum(c) (is_alpha(c) || is_digit(c)) static void Parse(void) { Token = T_UNDEF; Operator = O_UNDEF; if (Word) { free(Word); Word = NULL; } /* NULL expression? */ if (ExprPtr == NULL) { Word = strdup(""); return; } /* skip leading whitespace */ while (is_space(*ExprPtr)) ExprPtr++; /* names */ if (is_alpha(*ExprPtr)) { char *start = ExprPtr; while (is_alnum(*ExprPtr)) ExprPtr++; if (*ExprPtr == ':' && *(ExprPtr + 1) == ':' && is_alpha(*(ExprPtr + 2))) { ExprPtr += 3; while (is_alnum(*ExprPtr)) ExprPtr++; } Word = strndup(start, ExprPtr - start); Token = T_NAME; } /* numbers */ else if (is_digit(*ExprPtr) || (*ExprPtr == '.' && is_digit(*(ExprPtr + 1)))) { char *start = ExprPtr; while (is_digit(*ExprPtr)) ExprPtr++; if (*ExprPtr == '.') { ExprPtr++; while (is_digit(*ExprPtr)) ExprPtr++; } Word = strndup(start, ExprPtr - start); Token = T_NUMBER; } /* strings */ else if (*ExprPtr == '\'') { char *start = ++ExprPtr; while (*ExprPtr != '\0' && *ExprPtr != '\'') ExprPtr++; Word = strndup(start, ExprPtr - start); Token = T_STRING; if (*ExprPtr == '\'') ExprPtr++; } /* operators */ else { int i; for (i = sizeof(Pattern) / sizeof(Pattern[0]) - 1; i >= 0; i--) { int len = Pattern[i].len; if (strncmp(ExprPtr, Pattern[i].pattern, Pattern[i].len) == 0) { Word = strndup(ExprPtr, len); Token = T_OPERATOR; Operator = Pattern[i].op; ExprPtr += len; break; } } } /* syntax check */ if (Token == T_UNDEF && *ExprPtr != '\0') { error("Evaluator: parse error in <%s>: garbage <%s>", Expression, ExprPtr); } /* skip trailing whitespace */ while (is_space(*ExprPtr)) ExprPtr++; /* empty token */ if (Word == NULL) Word = strdup(""); } static NODE *NewNode(NODE * Child) { NODE *N; N = malloc(sizeof(NODE)); if (N == NULL) return NULL; memset(N, 0, sizeof(NODE)); N->Token = Token; N->Operator = Operator; if (Child != NULL) { N->Children = 1; N->Child = malloc(sizeof(NODE *)); N->Child[0] = Child; } return N; } static NODE *JunkNode(void) { NODE *Junk; Junk = NewNode(NULL); Junk->Token = T_STRING; SetResult(&Junk->Result, R_STRING, ""); return Junk; } static void LinkNode(NODE * Root, NODE * Child) { if (Child == NULL) return; Root->Children++; Root->Child = realloc(Root->Child, Root->Children * sizeof(NODE *)); if (Root->Child == NULL) return; Root->Child[Root->Children - 1] = Child; } /* forward declaration */ static NODE *Level01(void); /* literal numbers, variables, functions */ static NODE *Level12(void) { NODE *Root = NULL; if (Token == T_OPERATOR && Operator == O_BRO) { Parse(); Root = Level01(); if (Token != T_OPERATOR || Operator != O_BRC) { error("Evaluator: unbalanced parentheses in <%s>", Expression); LinkNode(Root, JunkNode()); } } else if (Token == T_NUMBER) { double value = atof(Word); Root = NewNode(NULL); SetResult(&Root->Result, R_NUMBER, &value); } else if (Token == T_STRING) { Root = NewNode(NULL); SetResult(&Root->Result, R_STRING, Word); } else if (Token == T_NAME) { /* look-ahead for opening brace */ if (*ExprPtr == '(') { int argc = 0; Root = NewNode(NULL); Root->Token = T_FUNCTION; Root->Result = NewResult(); Root->Function = FindFunction(Word); if (Root->Function == NULL) { error("Evaluator: unknown function '%s' in <%s>", Word, Expression); Root->Token = T_STRING; SetResult(&Root->Result, R_STRING, ""); } /* opening brace */ Parse(); do { Parse(); /* read argument */ if (Token == T_OPERATOR && Operator == O_BRC) { break; } else if (Token == T_OPERATOR && Operator == O_COM) { error("Evaluator: empty argument in <%s>", Expression); LinkNode(Root, JunkNode()); } else { LinkNode(Root, Level01()); } argc++; } while (Token == T_OPERATOR && Operator == O_COM); /* check for closing brace */ if (Token != T_OPERATOR || Operator != O_BRC) { error("Evaluator: missing closing brace in <%s>", Expression); } /* check number of arguments */ if (Root->Function != NULL && Root->Function->argc >= 0 && Root->Function->argc != argc) { error("Evaluator: wrong number of arguments in <%s>", Expression); while (argc < Root->Function->argc) { LinkNode(Root, JunkNode()); argc++; } } } else { Root = NewNode(NULL); Root->Token = T_VARIABLE; Root->Result = NewResult(); Root->Variable = FindVariable(Word); if (Root->Variable == NULL) { SetVariableString(Word, ""); Root->Variable = FindVariable(Word); } } } else { error("Evaluator: syntax error in <%s>: <%s>", Expression, Word); Root = NewNode(NULL); Root->Token = T_STRING; SetResult(&Root->Result, R_STRING, ""); } Parse(); return Root; } /* unary + or - signs or logical 'not' */ static NODE *Level11(void) { NODE *Root; TOKEN sign = T_UNDEF; if (Token == T_OPERATOR && (Operator == O_ADD || Operator == O_SUB || Operator == O_NOT)) { sign = Operator; if (sign == O_SUB) sign = O_SGN; Parse(); } Root = Level12(); if (sign == O_SGN || sign == O_NOT) { Root = NewNode(Root); Root->Token = T_OPERATOR; Root->Operator = sign; } return Root; } /* x^y */ static NODE *Level10(void) { NODE *Root; Root = Level11(); while (Token == T_OPERATOR && Operator == O_POW) { Root = NewNode(Root); Parse(); LinkNode(Root, Level11()); } return Root; } /* multiplication, division, modulo */ static NODE *Level09(void) { NODE *Root; Root = Level10(); while (Token == T_OPERATOR && (Operator == O_MUL || Operator == O_DIV || Operator == O_MOD)) { Root = NewNode(Root); Parse(); LinkNode(Root, Level10()); } return Root; } /* addition, subtraction, string concatenation */ static NODE *Level08(void) { NODE *Root; Root = Level09(); while (Token == T_OPERATOR && (Operator == O_ADD || Operator == O_SUB || Operator == O_CAT)) { Root = NewNode(Root); Parse(); LinkNode(Root, Level09()); } return Root; } /* relational operators */ static NODE *Level07(void) { NODE *Root; Root = Level08(); while (Token == T_OPERATOR && (Operator == O_GT || Operator == O_GE || Operator == O_LT || Operator == O_LE)) { Root = NewNode(Root); Parse(); LinkNode(Root, Level08()); } return Root; } /* equal, not equal */ static NODE *Level06(void) { NODE *Root; Root = Level07(); while (Token == T_OPERATOR && (Operator == O_EQ || Operator == O_NE)) { Root = NewNode(Root); Parse(); LinkNode(Root, Level07()); } return Root; } /* logical 'and' */ static NODE *Level05(void) { NODE *Root; Root = Level06(); while (Token == T_OPERATOR && Operator == O_AND) { Root = NewNode(Root); Parse(); LinkNode(Root, Level06()); } return Root; } /* logical 'or' */ static NODE *Level04(void) { NODE *Root; Root = Level05(); while (Token == T_OPERATOR && Operator == O_OR) { Root = NewNode(Root); Parse(); LinkNode(Root, Level05()); } return Root; } /* conditional expression a?b:c */ static NODE *Level03(void) { NODE *Root; Root = Level04(); if (Token == T_OPERATOR && Operator == O_CND) { Root = NewNode(Root); Parse(); LinkNode(Root, Level04()); if (Token == T_OPERATOR && Operator == O_COL) { Parse(); LinkNode(Root, Level04()); } else { error("Evaluator: syntax error in <%s>: expecting ':' got '%s'", Expression, Word); LinkNode(Root, JunkNode()); } } return Root; } /* variable assignments */ static NODE *Level02(void) { NODE *Root; /* we have to do a look-ahead if it's really an assignment */ if ((Token == T_NAME) && (*ExprPtr == '=') && (*(ExprPtr + 1) != '=')) { char *name = strdup(Word); VARIABLE *V = FindVariable(name); if (V == NULL) { SetVariableString(name, ""); V = FindVariable(name); } Parse(); Root = NewNode(NULL); Root->Variable = V; Parse(); LinkNode(Root, Level03()); free(name); } else { Root = Level03(); } return Root; } /* expression lists */ static NODE *Level01(void) { NODE *Root; Root = Level02(); while (Token == T_OPERATOR && Operator == O_LST) { Root = NewNode(Root); Parse(); LinkNode(Root, Level02()); } return Root; } static int EvalTree(NODE * Root) { int i; int argc; int type = -1; double number = 0.0; double dummy; int freeme = 0; char *string = NULL; char *s1, *s2; RESULT *param[10]; for (i = 0; i < Root->Children; i++) { EvalTree(Root->Child[i]); } switch (Root->Token) { case T_NUMBER: case T_STRING: /* Root->Result already contains the value */ return 0; case T_VARIABLE: DelResult(Root->Result); Root->Result = DupResult(Root->Variable->value); return 0; case T_FUNCTION: DelResult(Root->Result); /* prepare parameter list */ argc = Root->Children; if (argc > 10) argc = 10; for (i = 0; i < argc; i++) { param[i] = Root->Child[i]->Result; } if (Root->Function->argc < 0) { /* Function with variable argument list: */ /* pass number of arguments as first parameter */ Root->Function->func(Root->Result, argc, ¶m); } else { Root->Function->func(Root->Result, param[0], param[1], param[2], param[3], param[4], param[5], param[6], param[7], param[8], param[9]); } return 0; case T_OPERATOR: switch (Root->Operator) { case O_LST: /* expression list: result is last expression */ i = Root->Children - 1; type = Root->Child[i]->Result->type; number = Root->Child[i]->Result->number; string = Root->Child[i]->Result->string; break; case O_SET: /* variable assignment */ DelResult(Root->Variable->value); Root->Variable->value = DupResult(Root->Child[0]->Result); type = Root->Child[0]->Result->type; number = Root->Child[0]->Result->number; string = Root->Child[0]->Result->string; break; case O_CND: /* conditional expression */ i = 1 + (R2N(Root->Child[0]->Result) == 0.0); type = Root->Child[i]->Result->type; number = Root->Child[i]->Result->number; string = Root->Child[i]->Result->string; break; case O_OR: /* logical OR */ type = R_NUMBER; number = ((R2N(Root->Child[0]->Result) != 0.0) || (R2N(Root->Child[1]->Result) != 0.0)); break; case O_AND: /* logical AND */ type = R_NUMBER; number = ((R2N(Root->Child[0]->Result) != 0.0) && (R2N(Root->Child[1]->Result) != 0.0)); break; case O_EQ: /* numeric equal */ type = R_NUMBER; number = (R2N(Root->Child[0]->Result) == R2N(Root->Child[1]->Result)); break; case O_NE: /* numeric not equal */ type = R_NUMBER; number = (R2N(Root->Child[0]->Result) != R2N(Root->Child[1]->Result)); break; case O_LT: /* numeric less than */ type = R_NUMBER; number = (R2N(Root->Child[0]->Result) < R2N(Root->Child[1]->Result)); break; case O_LE: /* numeric less equal */ type = R_NUMBER; number = (R2N(Root->Child[0]->Result) <= R2N(Root->Child[1]->Result)); break; case O_GT: /* numeric greater than */ type = R_NUMBER; number = (R2N(Root->Child[0]->Result) > R2N(Root->Child[1]->Result)); break; case O_GE: /* numeric greater equal */ type = R_NUMBER; number = (R2N(Root->Child[0]->Result) >= R2N(Root->Child[1]->Result)); break; case O_ADD: /* addition */ type = R_NUMBER; number = R2N(Root->Child[0]->Result) + R2N(Root->Child[1]->Result); break; case O_SUB: /* subtraction */ type = R_NUMBER; number = R2N(Root->Child[0]->Result) - R2N(Root->Child[1]->Result); break; case O_SGN: /* sign */ type = R_NUMBER; number = -R2N(Root->Child[0]->Result); break; case O_CAT: /* string concatenation */ type = R_STRING; s1 = R2S(Root->Child[0]->Result); s2 = R2S(Root->Child[1]->Result); string = malloc(strlen(s1) + strlen(s2) + 1); strcpy(string, s1); strcat(string, s2); freeme = 1; break; case O_MUL: /* multiplication */ type = R_NUMBER; number = R2N(Root->Child[0]->Result) * R2N(Root->Child[1]->Result); break; case O_DIV: /* division */ type = R_NUMBER; dummy = R2N(Root->Child[1]->Result); if (dummy == 0) { error("Evaluator: warning: division by zero"); number = 0.0; } else { number = R2N(Root->Child[0]->Result) / R2N(Root->Child[1]->Result); } break; case O_MOD: /* modulo */ type = R_NUMBER; dummy = R2N(Root->Child[1]->Result); if (dummy == 0) { error("Evaluator: warning: division by zero"); number = 0.0; } else { number = fmod(R2N(Root->Child[0]->Result), R2N(Root->Child[1]->Result)); } break; case O_POW: /* x^y */ type = R_NUMBER; number = pow(R2N(Root->Child[0]->Result), R2N(Root->Child[1]->Result)); break; case O_NOT: /* logical NOT */ type = R_NUMBER; number = (R2N(Root->Child[0]->Result) == 0.0); break; default: error("Evaluator: internal error: unhandled operator <%d>", Root->Operator); SetResult(&Root->Result, R_STRING, ""); return -1; } if (type == R_NUMBER) { SetResult(&Root->Result, R_NUMBER, &number); return 0; } if (type == R_STRING) { SetResult(&Root->Result, R_STRING, string); if (freeme) free(string); return 0; } error("Evaluator: internal error: unhandled type <%d>", type); SetResult(&Root->Result, R_STRING, ""); return -1; default: error("Evaluator: internal error: unhandled token <%d>", Root->Token); SetResult(&Root->Result, R_STRING, ""); return -1; } return 0; } int Compile(const char *expression, void **tree) { NODE *Root; *tree = NULL; Expression = (char *) expression; ExprPtr = Expression; Parse(); if (*Word == '\0') { /* error ("Evaluator: empty expression <%s>", Expression); */ free(Word); Word = NULL; return -1; } Root = Level01(); if (*Word != '\0') { error("Evaluator: syntax error in <%s>: garbage <%s>", Expression, Word); free(Word); Word = NULL; return -1; } free(Word); Word = NULL; *(NODE **) tree = Root; return 0; } int Eval(void *tree, RESULT * result) { int ret; NODE *Tree = (NODE *) tree; DelResult(result); if (Tree == NULL) { SetResult(&result, R_STRING, ""); return 0; } ret = EvalTree(Tree); result->type = Tree->Result->type; result->number = Tree->Result->number; result->length = Tree->Result->length; if (result->length >= 0) { result->string = malloc(result->length); if (Tree->Result->string != NULL) strcpy(result->string, Tree->Result->string); else result->string[0] = '\0'; } else { result->string = NULL; } return ret; } void DelTree(void *tree) { int i; NODE *Tree = (NODE *) tree; if (Tree == NULL) return; for (i = 0; i < Tree->Children; i++) { DelTree(Tree->Child[i]); } if (Tree->Result) FreeResult(Tree->Result); free(Tree); }