--- /dev/null
+
+/*
+ * 1. build netdata (as normally)
+ * 2. cd profile/
+ * 3. compile with:
+ * gcc -O1 -ggdb -Wall -Wextra -I ../src/ -I ../ -o test-eval test-eval.c ../src/log.o ../src/eval.o ../src/common.o -pthread
+ *
+ */
+
+#include "common.h"
+
+void netdata_cleanup_and_exit(int ret) { exit(ret); }
+
+void indent(int level, int show) {
+ int i = level;
+ while(i--) printf(" | ");
+ if(show) printf(" \\_ ");
+ else printf(" \\_ ");
+}
+
+void print_operand(EVAL_OPERAND *op, int level);
+
+void print_value(EVAL_VALUE *v, int level) {
+ indent(level, 0);
+
+ switch(v->type) {
+ case EVAL_VALUE_INVALID:
+ printf("VALUE (NOP)\n");
+ break;
+
+ case EVAL_VALUE_NUMBER:
+ printf("VALUE %Lf (NUMBER)\n", v->number);
+ break;
+
+ case EVAL_VALUE_EXPRESSION:
+ printf("VALUE (SUB-EXPRESSION)\n");
+ print_operand(v->expression, level+1);
+ break;
+
+ default:
+ printf("VALUE (INVALID type %d)\n", v->type);
+ break;
+
+ }
+}
+
+void print_operand(EVAL_OPERAND *op, int level) {
+
+// if(op->operator != EVAL_OPERATOR_NOP) {
+ indent(level, 1);
+ if(op->operator) printf("%c (OPERATOR %d, prec: %d)\n", op->operator, op->id, op->precedence);
+ else printf("NOP (OPERATOR %d, prec: %d)\n", op->id, op->precedence);
+// }
+
+ int i = op->count;
+ while(i--) print_value(&op->ops[i], level + 1);
+}
+
+calculated_number evaluate(EVAL_OPERAND *op);
+
+calculated_number evaluate_value(EVAL_VALUE *v) {
+ switch(v->type) {
+ case EVAL_VALUE_NUMBER:
+ return v->number;
+
+ case EVAL_VALUE_EXPRESSION:
+ return evaluate(v->expression);
+
+ default:
+ fatal("I don't know how to handle EVAL_VALUE type %d", v->type);
+ }
+}
+
+calculated_number evaluate(EVAL_OPERAND *op) {
+ calculated_number n1, n2, r;
+
+ switch(op->operator) {
+ case EVAL_OPERATOR_SIGN_PLUS:
+ r = evaluate_value(&op->ops[0]);
+ break;
+
+ case EVAL_OPERATOR_SIGN_MINUS:
+ r = -evaluate_value(&op->ops[0]);
+ break;
+
+ case EVAL_OPERATOR_PLUS:
+ if(op->count != 2)
+ fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count);
+ n1 = evaluate_value(&op->ops[0]);
+ n2 = evaluate_value(&op->ops[1]);
+ r = n1 + n2;
+ printf("%Lf = %Lf %c %Lf\n", r, n1, op->operator, n2);
+ break;
+
+ case EVAL_OPERATOR_MINUS:
+ if(op->count != 2)
+ fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count);
+ n1 = evaluate_value(&op->ops[0]);
+ n2 = evaluate_value(&op->ops[1]);
+ r = n1 - n2;
+ printf("%Lf = %Lf %c %Lf\n", r, n1, op->operator, n2);
+ break;
+
+ case EVAL_OPERATOR_MULTIPLY:
+ if(op->count != 2)
+ fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count);
+ n1 = evaluate_value(&op->ops[0]);
+ n2 = evaluate_value(&op->ops[1]);
+ r = n1 * n2;
+ printf("%Lf = %Lf %c %Lf\n", r, n1, op->operator, n2);
+ break;
+
+ case EVAL_OPERATOR_DIVIDE:
+ if(op->count != 2)
+ fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count);
+ n1 = evaluate_value(&op->ops[0]);
+ n2 = evaluate_value(&op->ops[1]);
+ r = n1 / n2;
+ printf("%Lf = %Lf %c %Lf\n", r, n1, op->operator, n2);
+ break;
+
+ case EVAL_OPERATOR_EXPRESSION_OPEN:
+ printf("BEGIN SUB-EXPRESSION\n");
+ r = evaluate_value(&op->ops[0]);
+ printf("END SUB-EXPRESSION\n");
+ break;
+
+ case EVAL_OPERATOR_NOP:
+ case EVAL_OPERATOR_VALUE:
+ r = evaluate_value(&op->ops[0]);
+ break;
+
+ default:
+ fatal("I don't know how to handle operator '%c'", op->operator);
+ break;
+ }
+
+ return r;
+}
+
+void print_expression(EVAL_OPERAND *op, const char *failed_at, int error) {
+ if(op) {
+ printf("<expression root>\n");
+ print_operand(op, 0);
+ evaluate(op);
+ free_expression(op);
+ }
+ else {
+ printf("error: %d, failed_at: '%s'\n", error, (failed_at)?failed_at:"<NONE>");
+ }
+}
+
+
+int main(int argc, char **argv) {
+ if(argc != 2) {
+ fprintf(stderr, "I need an epxression\n");
+ exit(1);
+ }
+
+ const char *failed_at = NULL;
+ int error;
+ EVAL_OPERAND *op = parse_expression(argv[1], &failed_at, &error);
+ print_expression(op, failed_at, error);
+ return 0;
+}
#include "common.h"
+static inline void skip_spaces(const char **string) {
+ const char *s = *string;
+ while(isspace(*s)) s++;
+ *string = s;
+}
+
// ----------------------------------------------------------------------------
// operators that work on 2 operands
const char *s = *string;
// OR
- if((s[0] == 'O' || s[0] == '0') && (s[1] == 'R' || s[1] == 'r') && isoperatorterm_word(s[2])) {
+ if((s[0] == 'O' || s[0] == 'o') && (s[1] == 'R' || s[1] == 'r') && isoperatorterm_word(s[2])) {
*string = &s[3];
return 1;
}
return 0;
}
+static inline int parse_open_subexpression(const char **string) {
+ const char *s = *string;
+
+ // (
+ if(s[0] == '(') {
+ *string = &s[1];
+ return 1;
+ }
+
+ return 0;
+}
+
+static inline int parse_close_subexpression(const char **string) {
+ const char *s = *string;
+
+ // (
+ if(s[0] == ')') {
+ *string = &s[1];
+ return 1;
+ }
+
+ return 0;
+}
+
+static inline int parse_literal(const char **string, calculated_number *number) {
+ char *end = NULL;
+ *number = strtold(*string, &end);
+ if(!end || *string == end) return 0;
+
+ *string = end;
+ return 1;
+}
+
// ----------------------------------------------------------------------------
// operators that affect a single operand
// NOT
if((s[0] == 'N' || s[0] == 'n') && (s[1] == 'O' || s[1] == 'o') && (s[2] == 'T' || s[2] == 't') && isoperatorterm_word(s[3])) {
- *string = &s[4];
+ *string = &s[3];
return 1;
}
return 0;
}
-static struct operator {
- const char *printas;
- int precedence;
+static struct operator_parser {
char id;
int (*parse)(const char **);
-} operators[] = {
- { "&&", 2, '&', parse_and },
- { "||", 2, '|', parse_or },
- { ">=", 3, '}', parse_greater_than_or_equal },
- { "<=", 3, '{', parse_less_than_or_equal },
- { "<>", 3, '~', parse_not_equal },
- { "==", 3, '=', parse_equal },
- { "<", 3, '<', parse_less },
- { ">", 3, '>', parse_greater },
- { "+", 4, EVAL_OPERATOR_PLUS, parse_plus },
- { "-", 4, EVAL_OPERATOR_MINUS, parse_minus },
- { "*", 5, '*', parse_multiply },
- { "/", 5, '/', parse_divide },
-
- // we should not put NOT in this list
-
- { NULL, 0, EVAL_OPERATOR_NOP, NULL }
+} operator_parsers[] = {
+ // the order in this list is important!
+ // the first matching will be used
+ // so place the longer of overlapping ones
+ // at the top
+
+ { EVAL_OPERATOR_AND, parse_and },
+ { EVAL_OPERATOR_OR, parse_or },
+ { EVAL_OPERATOR_GREATER_THAN_OR_EQUAL, parse_greater_than_or_equal },
+ { EVAL_OPERATOR_LESS_THAN_OR_EQUAL, parse_less_than_or_equal },
+ { EVAL_OPERATOR_NOT_EQUAL, parse_not_equal },
+ { EVAL_OPERATOR_EQUAL, parse_equal },
+ { EVAL_OPERATOR_LESS, parse_less },
+ { EVAL_OPERATOR_GREATER, parse_greater },
+ { EVAL_OPERATOR_PLUS, parse_plus },
+ { EVAL_OPERATOR_MINUS, parse_minus },
+ { EVAL_OPERATOR_MULTIPLY, parse_multiply },
+ { EVAL_OPERATOR_DIVIDE, parse_divide },
+
+ /* we should not put
+ *
+ * - NOT
+ * - (
+ * - )
+ *
+ * in this list
+ */
+
+ { EVAL_OPERATOR_NOP, NULL }
};
-static inline char parse_operator(const char **s, int *precedence) {
- int i;
+// ----------------------------------------------------------------------------
+// evaluation of operations
+
+calculated_number eval_and(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_or(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_greater_than_or_equal(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_less_than_or_equal(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_not_equal(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_equal(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_less(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_greater(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_plus(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_minus(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_multiply(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_divide(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_nop(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_not(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_sign_plus(EVAL_OPERAND *op) {
+ return 0;
+}
+calculated_number eval_sign_minus(EVAL_OPERAND *op) {
+ return 0;
+}
+
+static struct operator {
+ const char *print_as;
+ char precedence;
+ calculated_number (*eval)(EVAL_OPERAND *op);
+} operators[256] = {
+ // this is a random access array
+ // we always access it with a known EVAL_OPERATOR_X
+
+ [EVAL_OPERATOR_AND] = { "&&", 2, eval_and },
+ [EVAL_OPERATOR_OR] = { "||", 2, eval_or },
+ [EVAL_OPERATOR_GREATER_THAN_OR_EQUAL] = { ">=", 3, eval_greater_than_or_equal },
+ [EVAL_OPERATOR_LESS_THAN_OR_EQUAL] = { "<=", 3, eval_less_than_or_equal },
+ [EVAL_OPERATOR_NOT_EQUAL] = { "!=", 3, eval_not_equal },
+ [EVAL_OPERATOR_EQUAL] = { "==", 3, eval_equal },
+ [EVAL_OPERATOR_LESS] = { "<", 3, eval_less },
+ [EVAL_OPERATOR_GREATER] = { ">", 3, eval_greater },
+ [EVAL_OPERATOR_PLUS] = { "+", 4, eval_plus },
+ [EVAL_OPERATOR_MINUS] = { "-", 4, eval_minus },
+ [EVAL_OPERATOR_MULTIPLY] = { "*", 5, eval_multiply },
+ [EVAL_OPERATOR_DIVIDE] = { "/", 5, eval_divide },
+ [EVAL_OPERATOR_NOT] = { "!", 6, eval_not },
+ [EVAL_OPERATOR_SIGN_PLUS] = { "+", 6, eval_sign_plus },
+ [EVAL_OPERATOR_SIGN_MINUS] = { "-", 6, eval_sign_minus },
+ [EVAL_OPERATOR_NOP] = { NULL, 7, eval_nop },
+ [EVAL_OPERATOR_VALUE] = { NULL, 7, eval_nop },
+ [EVAL_OPERATOR_EXPRESSION_OPEN] = { "(", 7, eval_nop },
+
+ // this should exist in our evaluation list
+ [EVAL_OPERATOR_EXPRESSION_CLOSE] = { ")", 7, eval_nop }
+};
+
+#define eval_precedence(operator) (operators[(unsigned char)(operator)].precedence)
- for(i = 0 ; operators[i].parse != NULL ; i++)
- if(operators[i].parse(s)) {
- if(precedence) *precedence = operators[i].precedence;
- return operators[i].id;
+// ----------------------------------------------------------------------------
+
+static inline char parse_operator(const char **string, int *precedence) {
+ skip_spaces(string);
+
+ int i;
+ for(i = 0 ; operator_parsers[i].parse != NULL ; i++)
+ if(operator_parsers[i].parse(string)) {
+ if(precedence) *precedence = eval_precedence(operator_parsers[i].id);
+ return operator_parsers[i].id;
}
return EVAL_OPERATOR_NOP;
}
+
static inline EVAL_OPERAND *operand_alloc(int count) {
+ static int id = 1;
+
EVAL_OPERAND *op = calloc(1, sizeof(EVAL_OPERAND) + (sizeof(EVAL_VALUE) * count));
- if(!op) fatal("Cannot allocate memory for OPERAND");
+ if(!op) fatal("Cannot allocate memory for OPERAND with %d slots", count);
+ op->id = id++;
+ op->operator = EVAL_OPERATOR_NOP;
+ op->precedence = eval_precedence(EVAL_OPERATOR_NOP);
op->count = count;
return op;
}
if(pos >= op->count)
fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
- op->ops[pos].type = EVAL_OPERAND_EXPRESSION;
+ op->ops[pos].type = EVAL_VALUE_EXPRESSION;
op->ops[pos].expression = value;
}
+static inline void operand_set_value_literal(EVAL_OPERAND *op, int pos, calculated_number value) {
+ if(pos >= op->count)
+ fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
+
+ op->ops[pos].type = EVAL_VALUE_NUMBER;
+ op->ops[pos].number = value;
+}
+
// forward definitions
-static inline EVAL_OPERAND *parse_operand(const char **string);
+static inline void operand_free(EVAL_OPERAND *op);
+static inline EVAL_OPERAND *parse_operand(const char **string, int *error);
+static inline EVAL_OPERAND *parse_operand1(const char **string, int *error);
+
+static inline void variable_free(VARIABLE *v) {
+ free(v);
+}
+
+static inline void value_free(EVAL_VALUE *v) {
+ switch(v->type) {
+ case EVAL_VALUE_EXPRESSION:
+ operand_free(v->expression);
+ break;
+
+ case EVAL_VALUE_VARIABLE:
+ variable_free(v->variable);
+ break;
+
+ default:
+ break;
+ }
+}
+
+static inline void operand_free(EVAL_OPERAND *op) {
+ if(op->count) {
+ int i;
+ for(i = op->count - 1; i >= 0 ;i--)
+ value_free(&op->ops[i]);
+ }
+
+ free(op);
+}
-static inline EVAL_OPERAND *operand_alloc_single(const char **string, char type) {
- EVAL_OPERAND *sub = parse_operand(string);
+static inline EVAL_OPERAND *parse_operand_with_operator(const char **string, char type, int *error) {
+ EVAL_OPERAND *sub = parse_operand1(string, error);
if(!sub) return NULL;
EVAL_OPERAND *op = operand_alloc(1);
- if(!op) fatal("Cannot allocate memory for OPERAND");
-
op->operator = type;
operand_set_value_operand(op, 0, sub);
return op;
}
-static inline EVAL_OPERAND *parse_operand(const char **string) {
- const char *s = *string;
- while(isspace(*s)) s++;
+static inline EVAL_OPERAND *parse_operand1(const char **string, int *error) {
+ EVAL_OPERAND *op1 = NULL;
+ calculated_number number;
- if(!*s) return NULL;
- *string = s;
+ *error = EVAL_ERROR_OK;
+
+ skip_spaces(string);
+ if(!(**string)) {
+ *error = EVAL_ERROR_MISSING_OPERAND;
+ return NULL;
+ }
+
+ if(parse_not(string)) {
+ op1 = parse_operand_with_operator(string, EVAL_OPERATOR_NOT, error);
+ op1->precedence = eval_precedence(EVAL_OPERATOR_NOT);
+ }
+ else if(parse_plus(string)) {
+ op1 = parse_operand_with_operator(string, EVAL_OPERATOR_SIGN_PLUS, error);
+ op1->precedence = eval_precedence(EVAL_OPERATOR_SIGN_PLUS);
+ }
+ else if(parse_minus(string)) {
+ op1 = parse_operand_with_operator(string, EVAL_OPERATOR_SIGN_MINUS, error);
+ op1->precedence = eval_precedence(EVAL_OPERATOR_SIGN_MINUS);
+ }
+ else if(parse_open_subexpression(string)) {
+ EVAL_OPERAND *sub = parse_operand(string, error);
+ if(sub) {
+ op1 = operand_alloc(1);
+ op1->operator = EVAL_OPERATOR_EXPRESSION_OPEN;
+ op1->precedence = eval_precedence(EVAL_OPERATOR_EXPRESSION_OPEN);
+ operand_set_value_operand(op1, 0, sub);
+ if(!parse_close_subexpression(string)) {
+ *error = EVAL_ERROR_MISSING_CLOSE_SUBEXPRESSION;
+ operand_free(op1);
+ return NULL;
+ }
+ }
+ }
+// else if(parse_variable(string)) {
+//
+// }
+ else if(parse_literal(string, &number)) {
+ op1 = operand_alloc(1);
+ op1->operator = EVAL_OPERATOR_VALUE;
+ operand_set_value_literal(op1, 0, number);
+ }
+ else if(*string)
+ *error = EVAL_ERROR_UNKNOWN_OPERAND;
+ else
+ *error = EVAL_ERROR_MISSING_OPERAND;
+
+ return op1;
+}
+
+static inline EVAL_OPERAND *parse_operand_rest(const char **string, int *error, EVAL_OPERAND *op1) {
+ EVAL_OPERAND *op2 = NULL;
+ char operator;
+ int precedence;
+
+ operator = parse_operator(string, &precedence);
+ skip_spaces(string);
+
+ if(operator != EVAL_OPERATOR_NOP) {
+ op2 = parse_operand1(string, error);
+ if(!op2) {
+ operand_free(op1);
+ return NULL;
+ }
+
+ EVAL_OPERAND *op = operand_alloc(2);
+ op->operator = operator;
+ op->precedence = precedence;
+
+ operand_set_value_operand(op, 0, op1);
+ operand_set_value_operand(op, 1, op2);
+
+ if(op->precedence > op1->precedence && op1->count == 2 && op1->operator != '(' && op1->ops[1].type == EVAL_VALUE_EXPRESSION) {
+ operand_set_value_operand(op, 0, op1->ops[1].expression);
+ op1->ops[1].expression = op;
+ op = op1;
+ }
+
+ return parse_operand_rest(string, error, op);
+ }
+ else if(**string == EVAL_OPERATOR_EXPRESSION_CLOSE) {
+ ;
+ }
+ else if(**string) {
+ if(op1) operand_free(op1);
+ op1 = NULL;
+ *error = EVAL_ERROR_MISSING_OPERATOR;
+ }
+
+ return op1;
+}
+
+static inline EVAL_OPERAND *parse_operand(const char **string, int *error) {
+ EVAL_OPERAND *op1 = NULL;
- if(parse_not(string))
- return operand_alloc_single(string, EVAL_OPERATOR_NOT);
+ op1 = parse_operand1(string, error);
+ if(!op1) {
+ *error = EVAL_ERROR_MISSING_OPERAND;
+ return NULL;
+ }
+
+ return parse_operand_rest(string, error, op1);
+}
- if(parse_plus(string))
- return operand_alloc_single(string, EVAL_OPERATOR_PLUS);
+const char *eval_error(int error) {
+ switch(error) {
+ case EVAL_ERROR_OK:
+ return "success";
- if(parse_minus(string))
- return operand_alloc_single(string, EVAL_OPERATOR_MINUS);
+ case EVAL_ERROR_MISSING_CLOSE_SUBEXPRESSION:
+ return "missing closing parenthesis";
+ case EVAL_ERROR_UNKNOWN_OPERAND:
+ return "unknown operand";
+ case EVAL_ERROR_MISSING_OPERAND:
+ return "expected operand";
+
+ case EVAL_ERROR_MISSING_OPERATOR:
+ return "expected operator";
+
+ default:
+ return "unknown error";
+ }
+}
+
+EVAL_OPERAND *parse_expression(const char *string, const char **failed_at, int *error) {
+ const char *s;
+ int err = EVAL_ERROR_OK;
+ unsigned long pos = 0;
+
+ s = string;
+ EVAL_OPERAND *op = parse_operand(&s, &err);
+
+ if (failed_at) *failed_at = s;
+ if (error) *error = err;
+
+ if(!op) {
+ pos = s - string + 1;
+ error("failed to parse expression '%s': %s at character %lu (i.e.: '%s').", string, eval_error(err), pos, s);
+ }
+
+ return op;
+}
- return NULL;
+void free_expression(EVAL_OPERAND *op) {
+ if(op) operand_free(op);
}
projects / netdata.git / commitdiff