- unsigned
- i,
- p=0, /* parenthesis nesting value */
- b=0; /* current breakpoint in expression string */
-
- gpointer tree;
-
- GString *current_option = g_string_new("");
- lttv_simple_expression current_expression;
-
- g_print("filter::lttv_filter_new()\n"); /* debug */
-
- /*
- * 1. parse expression
- * 2. construct binary tree
- * 3. return corresponding filter
- */
-
- /*
- * Binary tree memory allocation
- * - based upon a preliminary block size
- */
- gulong size = (strlen(expression)/6) * 1.5;
- tree = g_malloc(size*sizeof(lttv_filter_tree));
-
- /*
- * Parse entire expression and construct
- * the binary tree. There are two steps
- * in browsing that string
- * 1. finding boolean ops ( &,|,^,! ) and parenthesis
- * 2. finding simple expressions
- * - field path
- * - op ( >, <, =, >=, <=, !=)
- * - value
- */
-
- for(i=0;i<strlen(expression);i++) {
- switch(expression[i]) {
- /*
- * boolean operators
- */
- case '&': /* and */
- parse_simple_expression(current_option);
- g_print("%s\n",¤t_option);
- current_option = g_string_new("");
- break;
- case '|': /* or */
- g_print("%s\n",current_option);
- current_option = g_string_new("");
- break;
- case '^': /* xor */
- g_print("%s\n",current_option);
- current_option = g_string_new("");
- break;
- case '!': /* not, or not equal (math op) */
- if(expression[i+1] == '=') { /* != */
- current_expression.op = LTTV_FIELD_NE;
- i++;
- } else { /* ! */
- g_print("%s\n",current_option);
- current_option = g_string_new("");
- }
- break;
- case '(': /* start of parenthesis */
- p++;
- break;
- case ')': /* end of parenthesis */
- p--;
- break;
-
- /*
- * mathematic operators
- */
- case '<': /* lower, lower or equal */
- if(expression[i+1] == '=') { /* <= */
- i++;
- current_expression.op = LTTV_FIELD_LE;
- } else current_expression.op = LTTV_FIELD_LT;
- break;
- case '>': /* higher, higher or equal */
- if(expression[i+1] == '=') { /* >= */
- i++;
- current_expression.op = LTTV_FIELD_GE;
- } else current_expression.op = LTTV_FIELD_GT;
- break;
- case '=': /* equal */
- current_expression.op = LTTV_FIELD_EQ;
- break;
- default: /* concatening current string */
- g_string_append_c(current_option,expression[i]);
- }
- }
-
- if( p>0 ) {
- g_warning("Wrong filtering options, the string\n\"%s\"\n\
- is not valid due to parenthesis incorrect use",expression);
- return NULL;
- }
+ g_print("filter::lttv_filter_new()\n"); /* debug */
+
+ unsigned
+ i,
+ p_nesting=0, /* parenthesis nesting value */
+ b=0; /* current breakpoint in expression string */
+
+ /* trees */
+ lttv_filter_tree
+ *tree = lttv_filter_tree_new(), /* main tree */
+ *subtree = NULL, /* buffer for subtrees */
+ *t1, /* buffer #1 */
+ *t2; /* buffer #2 */
+
+ /*
+ * Tree Stack
+ * each element of the list
+ * is a sub tree created
+ * by the use of parenthesis in the
+ * global expression. The final tree
+ * will be the one left at the root of
+ * the list
+ */
+ GPtrArray *tree_stack = g_ptr_array_new();
+ g_ptr_array_add( tree_stack,(gpointer) tree );
+
+ /* temporary values */
+ GString *a_field_component = g_string_new("");
+ GPtrArray *a_field_path = NULL;
+
+ lttv_simple_expression a_simple_expression;
+
+ /*
+ * Parse entire expression and construct
+ * the binary tree. There are two steps
+ * in browsing that string
+ * 1. finding boolean ops " &,|,^,! " and parenthesis " {,(,[,],),} "
+ * 2. finding simple expressions
+ * - field path ( separated by dots )
+ * - op ( >, <, =, >=, <=, !=)
+ * - value ( integer, string ... )
+ * To spare computing time, the whole
+ * string is parsed in this loop for a
+ * O(n) complexity order.
+ *
+ * When encountering logical op &,|,^
+ * 1. parse the last value if any
+ * 2. create a new tree
+ * 3. add the expression (simple exp, or exp (subtree)) to the tree
+ * 4. concatenate this tree with the current tree on top of the stack
+ * When encountering math ops >,>=,<,<=,=,!=
+ * 1. add to op to the simple expression
+ * 2. concatenate last field component to field path
+ * When encountering concatening ops .
+ * 1. concatenate last field component to field path
+ * When encountering opening parenthesis (,{,[
+ * 1. create a new subtree on top of tree stack
+ * When encountering closing parenthesis ),},]
+ * 1. add the expression on right child of the current tree
+ * 2. the subtree is completed, allocate a new subtree
+ * 3. pop the tree value from the tree stack
+ */
+
+ a_field_path = g_ptr_array_new();
+ g_ptr_array_set_size(a_field_path,2); /* by default, recording 2 field expressions */
+
+
+ for(i=0;i<strlen(expression);i++) {
+// g_print("%s\n",a_field_component->str);
+ g_print("%c ",expression[i]);
+// g_print("switch:%c -->subtree:%p\n",expression[i],subtree);
+ switch(expression[i]) {
+ /*
+ * logical operators
+ */
+ case '&': /* and */
+ t1 = (lttv_filter_tree*)g_ptr_array_index(tree_stack,tree_stack->len-1);
+ while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
+ t2 = lttv_filter_tree_new();
+ t2->node->type = LTTV_EXPRESSION_OP;
+ t2->node->e.op = LTTV_LOGICAL_AND;
+ if(subtree != NULL) {
+ t2->left = LTTV_TREE_NODE;
+ t2->l_child.t = subtree;
+ subtree = NULL;
+ t1->right = LTTV_TREE_NODE;
+ t1->r_child.t = t2;
+ } else {
+ a_simple_expression.value = a_field_component->str;
+ a_field_component = g_string_new("");
+ t2->left = LTTV_TREE_LEAF;
+ t2->l_child.leaf = g_new(lttv_simple_expression,1);
+ t1->right = LTTV_TREE_NODE;
+ t1->r_child.t = t2;
+ }
+
+ break;
+ case '|': /* or */
+ t1 = (lttv_filter_tree*)g_ptr_array_index(tree_stack,tree_stack->len-1);
+ while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
+ t2 = lttv_filter_tree_new();
+ t2->node->type = LTTV_EXPRESSION_OP;
+ t2->node->e.op = LTTV_LOGICAL_OR;
+ if(subtree != NULL) {
+ t2->left = LTTV_TREE_NODE;
+ t2->l_child.t = subtree;
+ subtree = NULL;
+ t1->right = LTTV_TREE_NODE;
+ t1->r_child.t = t2;
+ } else {
+ a_simple_expression.value = a_field_component->str;
+ a_field_component = g_string_new("");
+ t2->left = LTTV_TREE_LEAF;
+ t2->l_child.leaf = g_new(lttv_simple_expression,1);
+ t1->right = LTTV_TREE_NODE;
+ t1->r_child.t = t2;
+ }
+ break;
+ case '^': /* xor */
+ t1 = (lttv_filter_tree*)g_ptr_array_index(tree_stack,tree_stack->len-1);
+ while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
+ t2 = lttv_filter_tree_new();
+ t2->node->type = LTTV_EXPRESSION_OP;
+ t2->node->e.op = LTTV_LOGICAL_XOR;
+ if(subtree != NULL) {
+ t2->left = LTTV_TREE_NODE;
+ t2->l_child.t = subtree;
+ subtree = NULL;
+ t1->right = LTTV_TREE_NODE;
+ t1->r_child.t = t2;
+ } else {
+ a_simple_expression.value = a_field_component->str;
+ a_field_component = g_string_new("");
+ t2->left = LTTV_TREE_LEAF;
+ t2->l_child.leaf = g_new(lttv_simple_expression,1);
+ t1->right = LTTV_TREE_NODE;
+ t1->r_child.t = t2;
+ }
+ break;
+ case '!': /* not, or not equal (math op) */
+ if(expression[i+1] == '=') { /* != */
+ a_simple_expression.op = LTTV_FIELD_NE;
+ i++;
+ } else { /* ! */
+ // g_print("%s\n",a_field_component);
+ // a_field_component = g_string_new("");
+ t1 = (lttv_filter_tree*)g_ptr_array_index(tree_stack,tree_stack->len-1);
+ while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
+ t2 = lttv_filter_tree_new();
+ t2->node->type = LTTV_EXPRESSION_OP;
+ t2->node->e.op = LTTV_LOGICAL_NOT;
+ t1->right = LTTV_TREE_NODE;
+ t1->r_child.t = t2;
+ }
+ break;
+ case '(': /* start of parenthesis */
+ case '[':
+ case '{':
+ p_nesting++; /* incrementing parenthesis nesting value */
+ t1 = lttv_filter_tree_new();
+ g_ptr_array_add( tree_stack,(gpointer) t1 );
+ break;
+ case ')': /* end of parenthesis */
+ case ']':
+ case '}':
+ p_nesting--; /* decrementing parenthesis nesting value */
+ if(p_nesting<0 || tree_stack->len<2) {
+ g_warning("Wrong filtering options, the string\n\"%s\"\n\
+ is not valid due to parenthesis incorrect use",expression);
+ return NULL;
+ }
+
+ g_assert(tree_stack->len>0);
+ if(subtree != NULL) {
+ t1 = g_ptr_array_index(tree_stack,tree_stack->len-1);
+ while(t1->right != LTTV_TREE_IDLE && t1->right != LTTV_TREE_LEAF) {
+ g_assert(t1!=NULL && t1->r_child.t != NULL);
+ t1 = t1->r_child.t;
+ }
+ t1->right = LTTV_TREE_NODE;
+ t1->r_child.t = subtree;
+ subtree = g_ptr_array_index(tree_stack,tree_stack->len-1);
+ g_ptr_array_remove_index(tree_stack,tree_stack->len-1);
+ } else {
+ a_simple_expression.value = a_field_component->str;
+ a_field_component = g_string_new("");
+ t1 = g_ptr_array_index(tree_stack,tree_stack->len-1);
+ while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
+ t1->right = LTTV_TREE_LEAF;
+ t1->r_child.leaf = g_new(lttv_simple_expression,1);
+ subtree = g_ptr_array_index(tree_stack,tree_stack->len-1);
+ g_assert(subtree != NULL);
+ g_ptr_array_remove_index(tree_stack,tree_stack->len-1);
+ }
+ break;
+
+ /*
+ * mathematic operators
+ */
+ case '<': /* lower, lower or equal */
+ if(expression[i+1] == '=') { /* <= */
+ i++;
+ a_simple_expression.op = LTTV_FIELD_LE;
+ } else a_simple_expression.op = LTTV_FIELD_LT;
+ g_ptr_array_add( a_field_path,(gpointer) a_field_component );
+ a_field_component = g_string_new("");
+ break;
+ case '>': /* higher, higher or equal */
+ if(expression[i+1] == '=') { /* >= */
+ i++;
+ a_simple_expression.op = LTTV_FIELD_GE;
+ } else a_simple_expression.op = LTTV_FIELD_GT;
+ g_ptr_array_add( a_field_path,(gpointer) a_field_component );
+ a_field_component = g_string_new("");
+ break;
+ case '=': /* equal */
+ a_simple_expression.op = LTTV_FIELD_EQ;
+ g_ptr_array_add( a_field_path,(gpointer) a_field_component );
+ a_field_component = g_string_new("");
+ break;
+ /*
+ * Field concatening caracter
+ */
+ case '.': /* dot */
+ g_ptr_array_add( a_field_path,(gpointer) a_field_component );
+ a_field_component = g_string_new("");
+ break;
+ default: /* concatening current string */
+ g_string_append_c(a_field_component,expression[i]);
+ }
+ }
+
+ g_print("subtree:%p, tree:%p, t1:%p, t2:%p\n",subtree,tree,t1,t2);
+
+ /* processing last element of expression */
+ g_assert(tree_stack->len==1); /* only root tree should remain */
+ t1 = g_ptr_array_index(tree_stack,tree_stack->len-1);
+ while(t1->right != LTTV_TREE_IDLE) t1 = t1->r_child.t;
+ if(subtree != NULL) { /* add the subtree */
+ t1->right = LTTV_TREE_NODE;
+ t1->l_child.t = subtree;
+ subtree = NULL;
+ } else { /* add a leaf */
+ a_simple_expression.value = a_field_component->str;
+ a_field_component = g_string_new("");
+ t1->right = LTTV_TREE_LEAF;
+ t1->r_child.leaf = g_new(lttv_simple_expression,1);
+ }
+
+ g_assert(tree != NULL);
+ g_assert(subtree == NULL);
+
+ if( p_nesting>0 ) {
+ g_warning("Wrong filtering options, the string\n\"%s\"\n\
+ is not valid due to parenthesis incorrect use",expression);
+ return NULL;
+ }
+
+ lttv_filter_tracefile(tree,NULL);
+
+ return tree;
+