ltt/branches/poly/lttv/lttv/filter.c

   1 /* This file is part of the Linux Trace Toolkit viewer
   2  * Copyright (C) 2003-2005 Michel Dagenais and Simon Bouvier-Zappa
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License Version 2 as
   6  * published by the Free Software Foundation;
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  16  * MA 02111-1307, USA.
  17  */
  18
  19 /*! \file lttv/lttv/filter.c
  20  *  \brief Defines the core filter of application
  21  *
  22  *  consist in AND, OR and NOT nested expressions, forming a tree with
  23  *  simple relations as leaves. The simple relations test if a field
  24  *  in an event is equal, not equal, smaller, smaller or equal, larger, or
  25  *  larger or equal to a specified value.
  26  *
  27  *  Fields specified in a simple expression can take following
  28  *  values
  29  *
  30  *  \verbatim
  31  *  LttvTracefileContext{}
  32  *  |->event\
  33  *  | |->name (String, converted to GQuark)
  34  *  | |->category (String, not yet implemented)
  35  *  | |->time (LttTime)
  36  *  | |->tsc (LttCycleCount --> uint64)
  37  *  | |->fields
  38  *  |   |->"event name"
  39  *  |     |->"field name"
  40  *  |       |->"sub-field name"
  41  *  |         |->...
  42  *  |           |->"leaf-field name" (field type)
  43  *  |->tracefile
  44  *  | |->name (String, converted to GQuark)
  45  *  |->trace
  46  *  | |->name (String, converted to GQuark)
  47  *  |->state
  48  *    |->pid (uint64)
  49  *    |->ppid (uint64)
  50  *    |->creation_time (LttTime)
  51  *    |->insertion_time (LttTime)
  52  *    |->process_name (String, converted to GQuark)
  53  *    |->execution_mode (LttvExecutionMode)
  54  *    |->execution_submode (LttvExecutionSubmode)
  55  *    |->process_status (LttvProcessStatus)
  56  *    |->cpu (GQuark)
  57  *  \endverbatim
  58  */
  59
  60 /*
  61  *  \todo
  62  *  - refine switch of expression in multiple uses functions
  63  *  - remove the idle expressions in the tree
  64  */
  65
  66 #ifdef HAVE_CONFIG_H
  67 #include <config.h>
  68 #endif
  69
  70 //#define TEST
  71 #ifdef TEST
  72 #include <time.h>
  73 #include <sys/time.h>
  74 #endif
  75
  76 #include <lttv/filter.h>
  77 #include <ltt/trace.h>
  78 #include <stdlib.h>
  79 #include <string.h>
  80
  81 /**
  82  * @fn LttvSimpleExpression* lttv_simple_expression_new()
  83  *
  84  * Constructor for LttvSimpleExpression
  85  * @return pointer to new LttvSimpleExpression
  86  */
  87 LttvSimpleExpression*
  88 lttv_simple_expression_new() {
  89
  90   LttvSimpleExpression* se = g_new(LttvSimpleExpression,1);
  91
  92   se->field = LTTV_FILTER_UNDEFINED;
  93   se->op = NULL;
  94   se->offset = 0;
  95
  96   return se;
  97 }
  98
  99 /**
 100  *  @fn gboolean lttv_simple_expression_assign_field(GPtrArray*,LttvSimpleExpression*)
 101  *
 102  *  Parse through filtering field hierarchy as specified
 103  *  by user.  This function compares each value to
 104  *  predetermined quarks
 105  *  @param fp The field path list
 106  *  @param se current simple expression
 107  *  @return success/failure of operation
 108  */
 109 gboolean
 110 lttv_simple_expression_assign_field(GPtrArray* fp, LttvSimpleExpression* se) {
 111
 112   GString* f = NULL;
 113
 114   if(fp->len < 2) return FALSE;
 115   g_assert((f=g_ptr_array_remove_index(fp,0)));
 116
 117   /*
 118    * Parse through the specified
 119    * hardcoded fields.
 120    *
 121    * Take note however that the
 122    * 'event' subfields might change
 123    * depending on values specified
 124    * in core.xml file.  Hence, if
 125    * none of the subfields in the
 126    * array match the hardcoded
 127    * subfields, it will be considered
 128    * as a dynamic field
 129    */
 130   if(!g_strcasecmp(f->str,"trace") ) {
 131     /*
 132      * Possible values:
 133      *  trace.name
 134      */
 135     g_string_free(f,TRUE);
 136     f=g_ptr_array_remove_index(fp,0);
 137     if(!g_strcasecmp(f->str,"name")) {
 138       se->field = LTTV_FILTER_TRACE_NAME;
 139     }
 140   } else if(!g_strcasecmp(f->str,"traceset") ) {
 141     /*
 142      * FIXME: not yet implemented !
 143      */
 144   } else if(!g_strcasecmp(f->str,"tracefile") ) {
 145     /*
 146      * Possible values:
 147      *  tracefile.name
 148      */
 149     g_string_free(f,TRUE);
 150     f=g_ptr_array_remove_index(fp,0);
 151     if(!g_strcasecmp(f->str,"name")) {
 152       se->field = LTTV_FILTER_TRACEFILE_NAME;
 153     }
 154   } else if(!g_strcasecmp(f->str,"state") ) {
 155     /*
 156      * Possible values:
 157      *  state.pid
 158      *  state.ppid
 159      *  state.creation_time
 160      *  state.insertion_time
 161      *  state.process_name
 162      *  state.execution_mode
 163      *  state.execution_submode
 164      *  state.process_status
 165      *  state.cpu
 166      */
 167     g_string_free(f,TRUE);
 168     f=g_ptr_array_remove_index(fp,0);
 169     if(!g_strcasecmp(f->str,"pid") ) {
 170       se->field = LTTV_FILTER_STATE_PID;
 171     }
 172     else if(!g_strcasecmp(f->str,"ppid") ) {
 173       se->field = LTTV_FILTER_STATE_PPID;
 174     }
 175     else if(!g_strcasecmp(f->str,"creation_time") ) {
 176       se->field = LTTV_FILTER_STATE_CT;
 177     }
 178     else if(!g_strcasecmp(f->str,"insertion_time") ) {
 179       se->field = LTTV_FILTER_STATE_IT;
 180     }
 181     else if(!g_strcasecmp(f->str,"process_name") ) {
 182       se->field = LTTV_FILTER_STATE_P_NAME;
 183     }
 184     else if(!g_strcasecmp(f->str,"execution_mode") ) {
 185       se->field = LTTV_FILTER_STATE_EX_MODE;
 186     }
 187     else if(!g_strcasecmp(f->str,"execution_submode") ) {
 188       se->field = LTTV_FILTER_STATE_EX_SUBMODE;
 189     }
 190     else if(!g_strcasecmp(f->str,"process_status") ) {
 191       se->field = LTTV_FILTER_STATE_P_STATUS;
 192     }
 193     else if(!g_strcasecmp(f->str,"cpu") ) {
 194       se->field = LTTV_FILTER_STATE_CPU;
 195     }
 196   } else if(!g_strcasecmp(f->str,"event") ) {
 197     /*
 198      * Possible values:
 199      *  event.name
 200      *  event.category
 201      *  event.time
 202      *  event.tsc
 203      */
 204     g_string_free(f,TRUE);
 205     f=g_ptr_array_remove_index(fp,0);
 206     if(!g_strcasecmp(f->str,"name") ) {
 207       se->field = LTTV_FILTER_EVENT_NAME;
 208     }
 209     else if(!g_strcasecmp(f->str,"category") ) {
 210       /*
 211        * FIXME: Category not yet functional in lttv
 212        */
 213       se->field = LTTV_FILTER_EVENT_CATEGORY;
 214     }
 215     else if(!g_strcasecmp(f->str,"time") ) {
 216       se->field = LTTV_FILTER_EVENT_TIME;
 217     }
 218     else if(!g_strcasecmp(f->str,"tsc") ) {
 219       se->field = LTTV_FILTER_EVENT_TSC;
 220     }
 221     else {  /* core.xml specified options */
 222       se->field = LTTV_FILTER_EVENT_FIELD;
 223     }
 224   } else {
 225     g_warning("Unrecognized field in filter string");
 226   }
 227
 228   /* free memory for last string */
 229   g_string_free(f,TRUE);
 230
 231   /* array should be empty */
 232   g_assert(fp->len == 0);
 233
 234   if(se->field == LTTV_FILTER_UNDEFINED) {
 235     g_warning("The specified field was not recognized !");
 236     return FALSE;
 237   }
 238   return TRUE;
 239 }
 240
 241 /**
 242  *  @fn gboolean lttv_simple_expression_assign_operator(LttvSimpleExpression*,LttvExpressionOp)
 243  *
 244  *  Sets the function pointer for the current
 245  *  Simple Expression
 246  *  @param se current simple expression
 247  *  @param op current operator
 248  *  @return success/failure of operation
 249  */
 250 gboolean
 251 lttv_simple_expression_assign_operator(LttvSimpleExpression* se, LttvExpressionOp op) {
 252
 253   switch(se->field) {
 254      /*
 255       * string
 256       */
 257      case LTTV_FILTER_TRACE_NAME:
 258      case LTTV_FILTER_TRACEFILE_NAME:
 259      case LTTV_FILTER_STATE_P_NAME:
 260      case LTTV_FILTER_EVENT_NAME:
 261      case LTTV_FILTER_STATE_CPU:
 262      case LTTV_FILTER_STATE_EX_MODE:
 263      case LTTV_FILTER_STATE_EX_SUBMODE:
 264      case LTTV_FILTER_STATE_P_STATUS:
 265        switch(op) {
 266          case LTTV_FIELD_EQ:
 267            se->op = lttv_apply_op_eq_quark;
 268            break;
 269          case LTTV_FIELD_NE:
 270            se->op = lttv_apply_op_ne_quark;
 271            break;
 272          default:
 273            g_warning("Error encountered in operator assignment = or != expected");
 274            return FALSE;
 275        }
 276        break;
 277      /*
 278       * integer
 279       */
 280      case LTTV_FILTER_STATE_PID:
 281      case LTTV_FILTER_STATE_PPID:
 282      case LTTV_FILTER_EVENT_TSC:
 283        switch(op) {
 284          case LTTV_FIELD_EQ:
 285            se->op = lttv_apply_op_eq_uint64;
 286            break;
 287          case LTTV_FIELD_NE:
 288            se->op = lttv_apply_op_ne_uint64;
 289            break;
 290          case LTTV_FIELD_LT:
 291            se->op = lttv_apply_op_lt_uint64;
 292            break;
 293          case LTTV_FIELD_LE:
 294            se->op = lttv_apply_op_le_uint64;
 295            break;
 296          case LTTV_FIELD_GT:
 297            se->op = lttv_apply_op_gt_uint64;
 298            break;
 299          case LTTV_FIELD_GE:
 300            se->op = lttv_apply_op_ge_uint64;
 301            break;
 302          default:
 303            g_warning("Error encountered in operator assignment");
 304            return FALSE;
 305        }
 306        break;
 307      /*
 308       * Enums
 309       * Entered as string, converted to enum
 310       *
 311       * can only be compared with 'equal' or 'not equal' operators
 312       *
 313       * unsigned int of 16 bits are used here since enums
 314       * should not go over 2^16-1 values
 315       */
 316 //      case /*NOTHING*/:
 317 //       switch(op) {
 318 //         case LTTV_FIELD_EQ:
 319 //           se->op = lttv_apply_op_eq_uint16;
 320 //           break;
 321 //         case LTTV_FIELD_NE:
 322 //           se->op = lttv_apply_op_ne_uint16;
 323 //           break;
 324 //         default:
 325 //           g_warning("Error encountered in operator assignment = or != expected");
 326 //           return FALSE;
 327 //       }
 328 //       break;
 329      /*
 330       * Ltttime
 331       */
 332      case LTTV_FILTER_STATE_CT:
 333      case LTTV_FILTER_STATE_IT:
 334      case LTTV_FILTER_EVENT_TIME:
 335        switch(op) {
 336          case LTTV_FIELD_EQ:
 337            se->op = lttv_apply_op_eq_ltttime;
 338            break;
 339          case LTTV_FIELD_NE:
 340            se->op = lttv_apply_op_ne_ltttime;
 341            break;
 342          case LTTV_FIELD_LT:
 343            se->op = lttv_apply_op_lt_ltttime;
 344            break;
 345          case LTTV_FIELD_LE:
 346            se->op = lttv_apply_op_le_ltttime;
 347            break;
 348          case LTTV_FIELD_GT:
 349            se->op = lttv_apply_op_gt_ltttime;
 350            break;
 351          case LTTV_FIELD_GE:
 352            se->op = lttv_apply_op_ge_ltttime;
 353            break;
 354          default:
 355            g_warning("Error encountered in operator assignment");
 356            return FALSE;
 357        }
 358        break;
 359      default:
 360        g_warning("Error encountered in operator assignation ! Field type:%i",se->field);
 361        return FALSE;
 362    }
 363
 364   return TRUE;
 365
 366 }
 367
 368 /**
 369  *  @fn gboolean lttv_simple_expression_assign_value(LttvSimpleExpression*,char*)
 370  *
 371  *  Assign the value field to the current LttvSimpleExpression
 372  *  @param se pointer to the current LttvSimpleExpression
 373  *  @param value string value for simple expression
 374  */
 375 gboolean
 376 lttv_simple_expression_assign_value(LttvSimpleExpression* se, char* value) {
 377
 378   unsigned i;
 379   gboolean is_double = FALSE;
 380   LttTime t = ltt_time_zero;
 381   GString* v;
 382
 383   switch(se->field) {
 384      /*
 385       * Strings
 386       * entered as strings, converted to Quarks
 387       */
 388      case LTTV_FILTER_TRACE_NAME:
 389      case LTTV_FILTER_TRACEFILE_NAME:
 390      case LTTV_FILTER_STATE_P_NAME:
 391      case LTTV_FILTER_EVENT_NAME:
 392      case LTTV_FILTER_STATE_CPU:
 393      case LTTV_FILTER_STATE_EX_MODE:
 394      case LTTV_FILTER_STATE_EX_SUBMODE:
 395      case LTTV_FILTER_STATE_P_STATUS:
 396       // se->value.v_string = value;
 397        se->value.v_uint32 = g_quark_from_string(value);
 398        g_free(value);
 399        break;
 400      /*
 401       * integer -- supposed to be uint64
 402       */
 403      case LTTV_FILTER_STATE_PID:
 404      case LTTV_FILTER_STATE_PPID:
 405      case LTTV_FILTER_EVENT_TSC:
 406        se->value.v_uint64 = atoi(value);
 407        g_free(value);
 408        break;
 409      /*
 410       * LttTime
 411       */
 412      case LTTV_FILTER_STATE_CT:
 413      case LTTV_FILTER_STATE_IT:
 414      case LTTV_FILTER_EVENT_TIME:
 415        //se->value.v_double = atof(value);
 416        /*
 417         * parsing logic could be optimised,
 418         * but as for now, simpler this way
 419         */
 420        v = g_string_new("");
 421        for(i=0;i<strlen(value);i++) {
 422           if(value[i] == '.') {
 423               /* cannot specify number with more than one '.' */
 424               if(is_double) return FALSE;
 425               else is_double = TRUE;
 426               t.tv_sec = atoi(v);
 427               g_string_free(v,TRUE);
 428               v = g_string_new("");
 429           } else g_string_append_c(v,value[i]);
 430        }
 431        /* number can be integer or double */
 432        if(is_double) t.tv_nsec = atoi(v);
 433        else t.tv_sec = atoi(v);
 434
 435        g_string_free(v,TRUE);
 436
 437        se->value.v_ltttime = t;
 438        g_free(value);
 439        break;
 440      default:
 441        g_warning("Error encountered in value assignation ! Field type = %i",se->field);
 442        g_free(value);
 443        return FALSE;
 444    }
 445
 446   return TRUE;
 447
 448 }
 449
 450 /**
 451  *  @fn void lttv_simple_expression_destroy(LttvSimpleExpression*)
 452  *
 453  *  Disallocate memory for the current
 454  *  simple expression
 455  *  @param se pointer to the current LttvSimpleExpression
 456  */
 457 void
 458 lttv_simple_expression_destroy(LttvSimpleExpression* se) {
 459
 460  // g_free(se->value);
 461 //  switch(se->field) {
 462 //     case LTTV_FILTER_TRACE_NAME:
 463 //     case LTTV_FILTER_TRACEFILE_NAME:
 464 //     case LTTV_FILTER_STATE_P_NAME:
 465 //     case LTTV_FILTER_EVENT_NAME:
 466 //       g_free(se->value.v_string);
 467 //       break;
 468 //  }
 469   g_free(se);
 470
 471 }
 472
 473 /**
 474  *  @fn gint lttv_struct_type(gint)
 475  *
 476  *  Finds the structure type depending
 477  *  on the fields in parameters
 478  *  @params ft Field of the current structure
 479  *  @return LttvStructType enum or -1 for error
 480  */
 481 gint
 482 lttv_struct_type(gint ft) {
 483
 484     switch(ft) {
 485         case LTTV_FILTER_TRACE_NAME:
 486             return LTTV_FILTER_TRACE;
 487             break;
 488         case LTTV_FILTER_TRACEFILE_NAME:
 489             return LTTV_FILTER_TRACEFILE;
 490             break;
 491         case LTTV_FILTER_STATE_PID:
 492         case LTTV_FILTER_STATE_PPID:
 493         case LTTV_FILTER_STATE_CT:
 494         case LTTV_FILTER_STATE_IT:
 495         case LTTV_FILTER_STATE_P_NAME:
 496         case LTTV_FILTER_STATE_EX_MODE:
 497         case LTTV_FILTER_STATE_EX_SUBMODE:
 498         case LTTV_FILTER_STATE_P_STATUS:
 499         case LTTV_FILTER_STATE_CPU:
 500             return LTTV_FILTER_STATE;
 501             break;
 502         case LTTV_FILTER_EVENT_NAME:
 503         case LTTV_FILTER_EVENT_CATEGORY:
 504         case LTTV_FILTER_EVENT_TIME:
 505         case LTTV_FILTER_EVENT_TSC:
 506         case LTTV_FILTER_EVENT_FIELD:
 507             return LTTV_FILTER_EVENT;
 508             break;
 509         default:
 510             return -1;
 511     }
 512 }
 513
 514 /**
 515  *  @fn gboolean lttv_apply_op_eq_uint64(gpointer,LttvFieldValue)
 516  *
 517  *  Applies the 'equal' operator to the
 518  *  specified structure and value
 519  *  @param v1 left member of comparison
 520  *  @param v2 right member of comparison
 521  *  @return success/failure of operation
 522  */
 523 gboolean lttv_apply_op_eq_uint64(const gpointer v1, LttvFieldValue v2) {
 524
 525   guint64* r = (guint64*) v1;
 526   return (*r == v2.v_uint64);
 527
 528 }
 529
 530 /**
 531  *  @fn gboolean lttv_apply_op_eq_uint32(gpointer,LttvFieldValue)
 532  *
 533  *  Applies the 'equal' operator to the
 534  *  specified structure and value
 535  *  @param v1 left member of comparison
 536  *  @param v2 right member of comparison
 537  *  @return success/failure of operation
 538  */
 539 gboolean lttv_apply_op_eq_uint32(const gpointer v1, LttvFieldValue v2) {
 540   guint32* r = (guint32*) v1;
 541   return (*r == v2.v_uint32);
 542 }
 543
 544 /**
 545  *  @fn gboolean lttv_apply_op_eq_uint16(gpointer,LttvFieldValue)
 546  *
 547  *  Applies the 'equal' operator to the
 548  *  specified structure and value
 549  *  @param v1 left member of comparison
 550  *  @param v2 right member of comparison
 551  *  @return success/failure of operation
 552  */
 553 gboolean lttv_apply_op_eq_uint16(const gpointer v1, LttvFieldValue v2) {
 554   guint16* r = (guint16*) v1;
 555   return (*r == v2.v_uint16);
 556 }
 557
 558 /**
 559  *  @fn gboolean lttv_apply_op_eq_double(gpointer,LttvFieldValue)
 560  *
 561  *  Applies the 'equal' operator to the
 562  *  specified structure and value
 563  *  @param v1 left member of comparison
 564  *  @param v2 right member of comparison
 565  *  @return success/failure of operation
 566  */
 567 gboolean lttv_apply_op_eq_double(const gpointer v1, LttvFieldValue v2) {
 568   double* r = (double*) v1;
 569   return (*r == v2.v_double);
 570 }
 571
 572 /**
 573  *  @fn gboolean lttv_apply_op_eq_string(gpointer,LttvFieldValue)
 574  *
 575  *  Applies the 'equal' operator to the
 576  *  specified structure and value
 577  *  @param v1 left member of comparison
 578  *  @param v2 right member of comparison
 579  *  @return success/failure of operation
 580  */
 581 gboolean lttv_apply_op_eq_string(const gpointer v1, LttvFieldValue v2) {
 582   char* r = (char*) v1;
 583   return (!g_strcasecmp(r,v2.v_string));
 584 }
 585
 586 /**
 587  *  @fn gboolean lttv_apply_op_eq_quark(gpointer,LttvFieldValue)
 588  *
 589  *  Applies the 'equal' operator to the
 590  *  specified structure and value
 591  *  @param v1 left member of comparison
 592  *  @param v2 right member of comparison
 593  *  @return success/failure of operation
 594  */
 595 gboolean lttv_apply_op_eq_quark(const gpointer v1, LttvFieldValue v2) {
 596   GQuark* r = (GQuark*) v1;
 597 //  g_print("v1:%i v2:%i\n",*r,v2.v_uint32);
 598   return (*r == v2.v_uint32);
 599 }
 600
 601 /**
 602  *  @fn gboolean lttv_apply_op_eq_ltttime(gpointer,LttvFieldValue)
 603  *
 604  *  Applies the 'equal' operator to the
 605  *  specified structure and value
 606  *  @param v1 left member of comparison
 607  *  @param v2 right member of comparison
 608  *  @return success/failure of operation
 609  */
 610 gboolean lttv_apply_op_eq_ltttime(const gpointer v1, LttvFieldValue v2) {
 611   LttTime* r = (LttTime*) v1;
 612   return ltt_time_compare(*r, v2.v_ltttime)==0?1:0;
 613 }
 614
 615
 616 /**
 617  *  @fn gboolean lttv_apply_op_ne_uint64(gpointer,LttvFieldValue)
 618  *
 619  *  Applies the 'not equal' operator to the
 620  *  specified structure and value
 621  *  @param v1 left member of comparison
 622  *  @param v2 right member of comparison
 623  *  @return success/failure of operation
 624  */
 625 gboolean lttv_apply_op_ne_uint64(const gpointer v1, LttvFieldValue v2) {
 626   guint64* r = (guint64*) v1;
 627   return (*r != v2.v_uint64);
 628 }
 629
 630 /**
 631  *  @fn gboolean lttv_apply_op_ne_uint32(gpointer,LttvFieldValue)
 632  *
 633  *  Applies the 'not equal' operator to the
 634  *  specified structure and value
 635  *  @param v1 left member of comparison
 636  *  @param v2 right member of comparison
 637  *  @return success/failure of operation
 638  */
 639 gboolean lttv_apply_op_ne_uint32(const gpointer v1, LttvFieldValue v2) {
 640   guint32* r = (guint32*) v1;
 641   return (*r != v2.v_uint32);
 642 }
 643
 644 /**
 645  *  @fn gboolean lttv_apply_op_ne_uint16(gpointer,LttvFieldValue)
 646  *
 647  *  Applies the 'not equal' operator to the
 648  *  specified structure and value
 649  *  @param v1 left member of comparison
 650  *  @param v2 right member of comparison
 651  *  @return success/failure of operation
 652  */
 653 gboolean lttv_apply_op_ne_uint16(const gpointer v1, LttvFieldValue v2) {
 654   guint16* r = (guint16*) v1;
 655   return (*r != v2.v_uint16);
 656 }
 657
 658 /**
 659  *  @fn gboolean lttv_apply_op_ne_double(gpointer,LttvFieldValue)
 660  *
 661  *  Applies the 'not equal' operator to the
 662  *  specified structure and value
 663  *  @param v1 left member of comparison
 664  *  @param v2 right member of comparison
 665  *  @return success/failure of operation
 666  */
 667 gboolean lttv_apply_op_ne_double(const gpointer v1, LttvFieldValue v2) {
 668   double* r = (double*) v1;
 669   return (*r != v2.v_double);
 670 }
 671
 672 /**
 673  *  @fn gboolean lttv_apply_op_ne_string(gpointer,LttvFieldValue)
 674  *
 675  *  Applies the 'not equal' operator to the
 676  *  specified structure and value
 677  *  @param v1 left member of comparison
 678  *  @param v2 right member of comparison
 679  *  @return success/failure of operation
 680  */
 681 gboolean lttv_apply_op_ne_string(const gpointer v1, LttvFieldValue v2) {
 682   char* r = (char*) v1;
 683   return (g_strcasecmp(r,v2.v_string));
 684 }
 685
 686 /**
 687  *  @fn gboolean lttv_apply_op_ne_quark(gpointer,LttvFieldValue)
 688  *
 689  *  Applies the 'not equal' operator to the
 690  *  specified structure and value
 691  *  @param v1 left member of comparison
 692  *  @param v2 right member of comparison
 693  *  @return success/failure of operation
 694  */
 695 gboolean lttv_apply_op_ne_quark(const gpointer v1, LttvFieldValue v2) {
 696   GQuark* r = (GQuark*) v1;
 697   return (*r != v2.v_uint32);
 698 }
 699
 700
 701 /**
 702  *  @fn gboolean lttv_apply_op_ne_ltttime(gpointer,LttvFieldValue)
 703  *
 704  *  Applies the 'not equal' operator to the
 705  *  specified structure and value
 706  *  @param v1 left member of comparison
 707  *  @param v2 right member of comparison
 708  *  @return success/failure of operation
 709  */
 710 gboolean lttv_apply_op_ne_ltttime(const gpointer v1, LttvFieldValue v2) {
 711   LttTime* r = (LttTime*) v1;
 712   return ltt_time_compare(*r, v2.v_ltttime)!=0?1:0;
 713 }
 714
 715
 716 /**
 717  *  @fn gboolean lttv_apply_op_lt_uint64(gpointer,LttvFieldValue)
 718  *
 719  *  Applies the 'lower than' operator to the
 720  *  specified structure and value
 721  *  @param v1 left member of comparison
 722  *  @param v2 right member of comparison
 723  *  @return success/failure of operation
 724  */
 725 gboolean lttv_apply_op_lt_uint64(const gpointer v1, LttvFieldValue v2) {
 726   guint64* r = (guint64*) v1;
 727   return (*r < v2.v_uint64);
 728 }
 729
 730 /**
 731  *  @fn gboolean lttv_apply_op_lt_uint32(gpointer,LttvFieldValue)
 732  *
 733  *  Applies the 'lower than' operator to the
 734  *  specified structure and value
 735  *  @param v1 left member of comparison
 736  *  @param v2 right member of comparison
 737  *  @return success/failure of operation
 738  */
 739 gboolean lttv_apply_op_lt_uint32(const gpointer v1, LttvFieldValue v2) {
 740   guint32* r = (guint32*) v1;
 741   return (*r < v2.v_uint32);
 742 }
 743
 744 /**
 745  *  @fn gboolean lttv_apply_op_lt_uint16(gpointer,LttvFieldValue)
 746  *
 747  *  Applies the 'lower than' operator to the
 748  *  specified structure and value
 749  *  @param v1 left member of comparison
 750  *  @param v2 right member of comparison
 751  *  @return success/failure of operation
 752  */
 753 gboolean lttv_apply_op_lt_uint16(const gpointer v1, LttvFieldValue v2) {
 754   guint16* r = (guint16*) v1;
 755   return (*r < v2.v_uint16);
 756 }
 757
 758 /**
 759  *  @fn gboolean lttv_apply_op_lt_double(gpointer,LttvFieldValue)
 760  *
 761  *  Applies the 'lower than' operator to the
 762  *  specified structure and value
 763  *  @param v1 left member of comparison
 764  *  @param v2 right member of comparison
 765  *  @return success/failure of operation
 766  */
 767 gboolean lttv_apply_op_lt_double(const gpointer v1, LttvFieldValue v2) {
 768   double* r = (double*) v1;
 769   return (*r < v2.v_double);
 770 }
 771
 772 /**
 773  *  @fn gboolean lttv_apply_op_lt_ltttime(gpointer,LttvFieldValue)
 774  *
 775  *  Applies the 'lower than' operator to the
 776  *  specified structure and value
 777  *  @param v1 left member of comparison
 778  *  @param v2 right member of comparison
 779  *  @return success/failure of operation
 780  */
 781 gboolean lttv_apply_op_lt_ltttime(const gpointer v1, LttvFieldValue v2) {
 782   LttTime* r = (LttTime*) v1;
 783 //  return ((r->tv_sec < v2.v_ltttime.tv_sec) || ((r->tv_sec == v2.v_ltttime.tv_sec) && (r->tv_nsec < v2.v_ltttime.tv_nsec)));
 784   return ltt_time_compare(*r, v2.v_ltttime)==-1?1:0;
 785 }
 786
 787
 788 /**
 789  *  @fn gboolean lttv_apply_op_le_uint64(gpointer,LttvFieldValue)
 790  *
 791  *  Applies the 'lower or equal' operator to the
 792  *  specified structure and value
 793  *  @param v1 left member of comparison
 794  *  @param v2 right member of comparison
 795  *  @return success/failure of operation
 796  */
 797 gboolean lttv_apply_op_le_uint64(const gpointer v1, LttvFieldValue v2) {
 798   guint64* r = (guint64*) v1;
 799   return (*r <= v2.v_uint64);
 800 }
 801
 802 /**
 803  *  @fn gboolean lttv_apply_op_le_uint32(gpointer,LttvFieldValue)
 804  *
 805  *  Applies the 'lower or equal' operator to the
 806  *  specified structure and value
 807  *  @param v1 left member of comparison
 808  *  @param v2 right member of comparison
 809  *  @return success/failure of operation
 810  */
 811 gboolean lttv_apply_op_le_uint32(const gpointer v1, LttvFieldValue v2) {
 812   guint32* r = (guint32*) v1;
 813   return (*r <= v2.v_uint32);
 814 }
 815
 816 /**
 817  *  @fn gboolean lttv_apply_op_le_uint16(gpointer,LttvFieldValue)
 818  *
 819  *  Applies the 'lower or equal' operator to the
 820  *  specified structure and value
 821  *  @param v1 left member of comparison
 822  *  @param v2 right member of comparison
 823  *  @return success/failure of operation
 824  */
 825 gboolean lttv_apply_op_le_uint16(const gpointer v1, LttvFieldValue v2) {
 826   guint16* r = (guint16*) v1;
 827   return (*r <= v2.v_uint16);
 828 }
 829
 830 /**
 831  *  @fn gboolean lttv_apply_op_le_double(gpointer,LttvFieldValue)
 832  *
 833  *  Applies the 'lower or equal' operator to the
 834  *  specified structure and value
 835  *  @param v1 left member of comparison
 836  *  @param v2 right member of comparison
 837  *  @return success/failure of operation
 838  */
 839 gboolean lttv_apply_op_le_double(const gpointer v1, LttvFieldValue v2) {
 840   double* r = (double*) v1;
 841   return (*r <= v2.v_double);
 842 }
 843
 844 /**
 845  *  @fn gboolean lttv_apply_op_le_ltttime(gpointer,LttvFieldValue)
 846  *
 847  *  Applies the 'lower or equal' operator to the
 848  *  specified structure and value
 849  *  @param v1 left member of comparison
 850  *  @param v2 right member of comparison
 851  *  @return success/failure of operation
 852  */
 853 gboolean lttv_apply_op_le_ltttime(const gpointer v1, LttvFieldValue v2) {
 854   LttTime* r = (LttTime*) v1;
 855 //  return ((r->tv_sec < v2.v_ltttime.tv_sec) || ((r->tv_sec == v2.v_ltttime.tv_sec) && (r->tv_nsec <= v2.v_ltttime.tv_nsec)));
 856   return ltt_time_compare(*r, v2.v_ltttime)<1?1:0;
 857 }
 858
 859
 860 /**
 861  *  @fn gboolean lttv_apply_op_gt_uint64(gpointer,LttvFieldValue)
 862  *
 863  *  Applies the 'greater than' operator to the
 864  *  specified structure and value
 865  *  @param v1 left member of comparison
 866  *  @param v2 right member of comparison
 867  *  @return success/failure of operation
 868  */
 869 gboolean lttv_apply_op_gt_uint64(const gpointer v1, LttvFieldValue v2) {
 870   guint64* r = (guint64*) v1;
 871   return (*r > v2.v_uint64);
 872 }
 873
 874 /**
 875  *  @fn gboolean lttv_apply_op_gt_uint32(gpointer,LttvFieldValue)
 876  *
 877  *  Applies the 'greater than' operator to the
 878  *  specified structure and value
 879  *  @param v1 left member of comparison
 880  *  @param v2 right member of comparison
 881  *  @return success/failure of operation
 882  */
 883 gboolean lttv_apply_op_gt_uint32(const gpointer v1, LttvFieldValue v2) {
 884   guint32* r = (guint32*) v1;
 885   return (*r > v2.v_uint32);
 886 }
 887
 888 /**
 889  *  @fn gboolean lttv_apply_op_gt_uint16(gpointer,LttvFieldValue)
 890  *
 891  *  Applies the 'greater than' operator to the
 892  *  specified structure and value
 893  *  @param v1 left member of comparison
 894  *  @param v2 right member of comparison
 895  *  @return success/failure of operation
 896  */
 897 gboolean lttv_apply_op_gt_uint16(const gpointer v1, LttvFieldValue v2) {
 898   guint16* r = (guint16*) v1;
 899   return (*r > v2.v_uint16);
 900 }
 901
 902 /**
 903  *  @fn gboolean lttv_apply_op_gt_double(gpointer,LttvFieldValue)
 904  *
 905  *  Applies the 'greater than' operator to the
 906  *  specified structure and value
 907  *  @param v1 left member of comparison
 908  *  @param v2 right member of comparison
 909  *  @return success/failure of operation
 910  */
 911 gboolean lttv_apply_op_gt_double(const gpointer v1, LttvFieldValue v2) {
 912   double* r = (double*) v1;
 913   return (*r > v2.v_double);
 914 }
 915
 916 /**
 917  *  @fn gboolean lttv_apply_op_gt_ltttime(gpointer,LttvFieldValue)
 918  *
 919  *  Applies the 'greater than' operator to the
 920  *  specified structure and value
 921  *  @param v1 left member of comparison
 922  *  @param v2 right member of comparison
 923  *  @return success/failure of operation
 924  */
 925 gboolean lttv_apply_op_gt_ltttime(const gpointer v1, LttvFieldValue v2) {
 926   LttTime* r = (LttTime*) v1;
 927 //  return ((r->tv_sec > v2.v_ltttime.tv_sec) || ((r->tv_sec == v2.v_ltttime.tv_sec) && (r->tv_nsec > v2.v_ltttime.tv_nsec)));
 928   return ltt_time_compare(*r, v2.v_ltttime)==1?1:0;
 929 }
 930
 931
 932 /**
 933  *  @fn gboolean lttv_apply_op_ge_uint64(gpointer,LttvFieldValue)
 934  *
 935  *  Applies the 'greater or equal' operator to the
 936  *  specified structure and value
 937  *  @param v1 left member of comparison
 938  *  @param v2 right member of comparison
 939  *  @return success/failure of operation
 940  */
 941 gboolean lttv_apply_op_ge_uint64(const gpointer v1, LttvFieldValue v2) {
 942   guint64* r = (guint64*) v1;
 943   return (*r >= v2.v_uint64);
 944 }
 945
 946 /**
 947  *  @fn gboolean lttv_apply_op_ge_uint32(gpointer,LttvFieldValue)
 948  *
 949  *  Applies the 'greater or equal' operator to the
 950  *  specified structure and value
 951  *  @param v1 left member of comparison
 952  *  @param v2 right member of comparison
 953  *  @return success/failure of operation
 954  */
 955 gboolean lttv_apply_op_ge_uint32(const gpointer v1, LttvFieldValue v2) {
 956   guint32* r = (guint32*) v1;
 957   return (*r >= v2.v_uint32);
 958 }
 959
 960 /**
 961  *  @fn gboolean lttv_apply_op_ge_uint16(gpointer,LttvFieldValue)
 962  *
 963  *  Applies the 'greater or equal' operator to the
 964  *  specified structure and value
 965  *  @param v1 left member of comparison
 966  *  @param v2 right member of comparison
 967  *  @return success/failure of operation
 968  */
 969 gboolean lttv_apply_op_ge_uint16(const gpointer v1, LttvFieldValue v2) {
 970   guint16* r = (guint16*) v1;
 971   return (*r >= v2.v_uint16);
 972 }
 973
 974 /**
 975  *  @fn gboolean lttv_apply_op_ge_double(gpointer,LttvFieldValue)
 976  *
 977  *  Applies the 'greater or equal' operator to the
 978  *  specified structure and value
 979  *  @param v1 left member of comparison
 980  *  @param v2 right member of comparison
 981  *  @return success/failure of operation
 982  */
 983 gboolean lttv_apply_op_ge_double(const gpointer v1, LttvFieldValue v2) {
 984   double* r = (double*) v1;
 985   return (*r >= v2.v_double);
 986 }
 987
 988 /**
 989  *  @fn gboolean lttv_apply_op_ge_ltttime(gpointer,LttvFieldValue)
 990  *
 991  *  Applies the 'greater or equal' operator to the
 992  *  specified structure and value
 993  *  @param v1 left member of comparison
 994  *  @param v2 right member of comparison
 995  *  @return success/failure of operation
 996  */
 997 gboolean lttv_apply_op_ge_ltttime(const gpointer v1, LttvFieldValue v2) {
 998   LttTime* r = (LttTime*) v1;
 999 //  return ((r->tv_sec > v2.v_ltttime.tv_sec) || ((r->tv_sec == v2.v_ltttime.tv_sec) && (r->tv_nsec >= v2.v_ltttime.tv_nsec)));
1000   return ltt_time_compare(*r, v2.v_ltttime)>-1?1:0;
1001 }
1002
1003
1004
1005 /**
1006  *  Makes a copy of the current filter tree
1007  *  @param tree pointer to the current tree
1008  *  @return new copy of the filter tree
1009  */
1010 LttvFilterTree*
1011 lttv_filter_tree_clone(const LttvFilterTree* tree) {
1012
1013   LttvFilterTree* newtree = lttv_filter_tree_new();
1014
1015   newtree->node = tree->node;
1016
1017   newtree->left = tree->left;
1018   if(newtree->left == LTTV_TREE_NODE) {
1019     newtree->l_child.t = lttv_filter_tree_clone(tree->l_child.t);
1020   } else if(newtree->left == LTTV_TREE_LEAF) {
1021     newtree->l_child.leaf = lttv_simple_expression_new();
1022     newtree->l_child.leaf->field = tree->l_child.leaf->field;
1023     newtree->l_child.leaf->offset = tree->l_child.leaf->offset;
1024     newtree->l_child.leaf->op = tree->l_child.leaf->op;
1025     /* FIXME: special case for string copy ! */
1026     newtree->l_child.leaf->value = tree->l_child.leaf->value;
1027   }
1028
1029   newtree->right = tree->right;
1030   if(newtree->right == LTTV_TREE_NODE) {
1031     newtree->r_child.t = lttv_filter_tree_clone(tree->r_child.t);
1032   } else if(newtree->right == LTTV_TREE_LEAF) {
1033     newtree->r_child.leaf = lttv_simple_expression_new();
1034     newtree->r_child.leaf->field = tree->r_child.leaf->field;
1035     newtree->r_child.leaf->offset = tree->r_child.leaf->offset;
1036     newtree->r_child.leaf->op = tree->r_child.leaf->op;
1037     newtree->r_child.leaf->value = tree->r_child.leaf->value;
1038   }
1039
1040   return newtree;
1041
1042 }
1043
1044 /**
1045  *  Makes a copy of the current filter
1046  *  @param filter pointer to the current filter
1047  *  @return new copy of the filter
1048  */
1049 LttvFilter*
1050 lttv_filter_clone(const LttvFilter* filter) {
1051
1052         if(!filter) return NULL;
1053
1054   LttvFilter* newfilter = g_new(LttvFilter,1);
1055
1056   strcpy(newfilter->expression,filter->expression);
1057
1058   newfilter->head = lttv_filter_tree_clone(filter->head);
1059
1060   return newfilter;
1061
1062 }
1063
1064
1065 /**
1066  *  @fn LttvFilter* lttv_filter_new()
1067  *
1068  *      Creates a new LttvFilter
1069  *      @return the current LttvFilter or NULL if error
1070  */
1071 LttvFilter*
1072 lttv_filter_new() {
1073
1074   LttvFilter* filter = g_new(LttvFilter,1);
1075   filter->expression = NULL;
1076   filter->head = NULL;
1077
1078   return filter;
1079
1080 }
1081
1082 /**
1083  *  @fn gboolean lttv_filter_update(LttvFilter*)
1084  *
1085  *  Updates the current LttvFilter by building
1086  *  its tree based upon the expression string
1087  *  @param filter pointer to the current LttvFilter
1088  *  @return Failure/Success of operation
1089  */
1090 gboolean
1091 lttv_filter_update(LttvFilter* filter) {
1092
1093 //  g_print("filter::lttv_filter_new()\n");             /* debug */
1094
1095   if(filter->expression == NULL) return FALSE;
1096
1097   int
1098     i,
1099     p_nesting=0,        /* parenthesis nesting value */
1100     not=0;
1101
1102   /* trees */
1103   LttvFilterTree
1104     *tree = lttv_filter_tree_new(),   /* main tree */
1105     *subtree = NULL,                  /* buffer for subtrees */
1106     *t1,                              /* buffer #1 */
1107     *t2,                              /* buffer #2 */
1108     *t3;                              /* buffer #3 */
1109
1110   /*
1111    * the filter
1112    * If the tree already exists,
1113    * destroy it and build a new one
1114    */
1115   if(filter->head != NULL) lttv_filter_tree_destroy(filter->head);
1116   filter->head = NULL;    /* will be assigned at the end */
1117
1118   /*
1119    * Tree Stack
1120    * each element of the list
1121    * is a sub tree created
1122    * by the use of parenthesis in the
1123    * global expression.  The final tree
1124    * will be the one left at the root of
1125    * the list
1126    */
1127   GPtrArray *tree_stack = g_ptr_array_new();
1128   g_ptr_array_add( tree_stack,(gpointer) tree );
1129
1130   /* temporary values */
1131   GString *a_field_component = g_string_new("");
1132   GPtrArray *a_field_path = g_ptr_array_new();
1133
1134   /* simple expression buffer */
1135   LttvSimpleExpression* a_simple_expression = lttv_simple_expression_new();
1136
1137   /*
1138    *    Parse entire expression and construct
1139    *    the binary tree.  There are two steps
1140    *    in browsing that string
1141    *      1. finding boolean ops " &,|,^,! " and parenthesis " {,(,[,],),} "
1142    *      2. finding simple expressions
1143    *        - field path ( separated by dots )
1144    *        - op ( >, <, =, >=, <=, !=)
1145    *        - value ( integer, string ... )
1146    *    To spare computing time, the whole
1147    *    string is parsed in this loop for a
1148    *    O(n) complexity order.
1149    *
1150    *  When encountering logical op &,|,^
1151    *    1. parse the last value if any
1152    *    2. create a new tree
1153    *    3. add the expression (simple exp, or exp (subtree)) to the tree
1154    *    4. concatenate this tree with the current tree on top of the stack
1155    *  When encountering math ops >,>=,<,<=,=,!=
1156    *    1. add to op to the simple expression
1157    *    2. concatenate last field component to field path
1158    *  When encountering concatening ops .
1159    *    1. concatenate last field component to field path
1160    *  When encountering opening parenthesis (,{,[
1161    *    1. create a new subtree on top of tree stack
1162    *  When encountering closing parenthesis ),},]
1163    *    1. add the expression on right child of the current tree
1164    *    2. the subtree is completed, allocate a new subtree
1165    *    3. pop the tree value from the tree stack
1166    */
1167
1168 #ifdef TEST
1169   struct timeval starttime;
1170   struct timeval endtime;
1171   gettimeofday(&starttime, NULL);
1172 #endif
1173
1174   for(i=0;i<strlen(filter->expression);i++) {
1175     // debug
1176 //    g_print("%c\n ",filter->expression[i]);
1177
1178     switch(filter->expression[i]) {
1179       /*
1180        *   logical operators
1181        */
1182       case '&':   /* and */
1183
1184         /* get current tree in tree stack */
1185         t1 = (LttvFilterTree*)g_ptr_array_index(tree_stack,tree_stack->len-1);
1186
1187         /* get current node at absolute right */
1188         while(t1->right != LTTV_TREE_IDLE) {
1189           g_assert(t1->right == LTTV_TREE_NODE);
1190           t1 = t1->r_child.t;
1191         }
1192         t2 = lttv_filter_tree_new();
1193         t2->node = LTTV_LOGICAL_AND;
1194         t1->right = LTTV_TREE_NODE;
1195         t1->r_child.t = t2;
1196         if(not) {   /* add not operator to tree */
1197           t3 = lttv_filter_tree_new();
1198           t3->node = LTTV_LOGICAL_NOT;
1199           t2->left = LTTV_TREE_NODE;
1200           t2->l_child.t = t3;
1201           t2 = t3;
1202           not = 0;
1203         }
1204         if(subtree != NULL) {   /* append subtree to current tree */
1205           t2->left = LTTV_TREE_NODE;
1206           t2->l_child.t = subtree;
1207           subtree = NULL;
1208         } else {  /* append a simple expression */
1209           lttv_simple_expression_assign_value(a_simple_expression,g_string_free(a_field_component,FALSE));
1210           a_field_component = g_string_new("");
1211           t2->left = LTTV_TREE_LEAF;
1212           t2->l_child.leaf = a_simple_expression;
1213           a_simple_expression = lttv_simple_expression_new();
1214         }
1215         break;
1216
1217       case '|':   /* or */
1218
1219         t1 = (LttvFilterTree*)g_ptr_array_index(tree_stack,tree_stack->len-1);
1220          while(t1->right != LTTV_TREE_IDLE) {
1221           g_assert(t1->right == LTTV_TREE_NODE);
1222           t1 = t1->r_child.t;
1223         }
1224         t2 = lttv_filter_tree_new();
1225         t2->node = LTTV_LOGICAL_OR;
1226         t1->right = LTTV_TREE_NODE;
1227         t1->r_child.t = t2;
1228         if(not) { // add not operator to tree
1229           t3 = lttv_filter_tree_new();
1230           t3->node = LTTV_LOGICAL_NOT;
1231           t2->left = LTTV_TREE_NODE;
1232           t2->l_child.t = t3;
1233           t2 = t3;
1234           not = 0;
1235        }
1236        if(subtree != NULL) {   /* append subtree to current tree */
1237           t2->left = LTTV_TREE_NODE;
1238           t2->l_child.t = subtree;
1239           subtree = NULL;
1240        } else {    /* append a simple expression */
1241           lttv_simple_expression_assign_value(a_simple_expression,g_string_free(a_field_component,FALSE));
1242           a_field_component = g_string_new("");
1243           t2->left = LTTV_TREE_LEAF;
1244           t2->l_child.leaf = a_simple_expression;
1245           a_simple_expression = lttv_simple_expression_new();
1246         }
1247         break;
1248
1249       case '^':   /* xor */
1250
1251         t1 = (LttvFilterTree*)g_ptr_array_index(tree_stack,tree_stack->len-1);
1252         while(t1->right != LTTV_TREE_IDLE) {
1253           g_assert(t1->right == LTTV_TREE_NODE);
1254           t1 = t1->r_child.t;
1255         }
1256         t2 = lttv_filter_tree_new();
1257         t2->node = LTTV_LOGICAL_XOR;
1258         t1->right = LTTV_TREE_NODE;
1259         t1->r_child.t = t2;
1260         if(not) { // add not operator to tree
1261           t3 = lttv_filter_tree_new();
1262           t3->node = LTTV_LOGICAL_NOT;
1263           t2->left = LTTV_TREE_NODE;
1264           t2->l_child.t = t3;
1265           t2 = t3;
1266           not = 0;
1267         }
1268         if(subtree != NULL) {   /* append subtree to current tree */
1269           t2->left = LTTV_TREE_NODE;
1270           t2->l_child.t = subtree;
1271           subtree = NULL;
1272         } else {    /* append a simple expression */
1273           lttv_simple_expression_assign_value(a_simple_expression,g_string_free(a_field_component,FALSE));
1274           a_field_component = g_string_new("");
1275           t2->left = LTTV_TREE_LEAF;
1276           t2->l_child.leaf = a_simple_expression;
1277           a_simple_expression = lttv_simple_expression_new();
1278         }
1279         break;
1280
1281       case '!':   /* not, or not equal (math op) */
1282
1283         if(filter->expression[i+1] == '=') {  /* != */
1284           g_ptr_array_add( a_field_path,(gpointer) a_field_component );
1285           lttv_simple_expression_assign_field(a_field_path,a_simple_expression);
1286           a_field_component = g_string_new("");
1287           lttv_simple_expression_assign_operator(a_simple_expression,LTTV_FIELD_NE);
1288           i++;
1289         } else {  /* ! */
1290           not=1;
1291         }
1292         break;
1293
1294       case '(':   /* start of parenthesis */
1295       case '[':
1296       case '{':
1297
1298         p_nesting++;      /* incrementing parenthesis nesting value */
1299         t1 = lttv_filter_tree_new();
1300         if(not) { /* add not operator to tree */
1301           t3 = lttv_filter_tree_new();
1302           t3->node = LTTV_LOGICAL_NOT;
1303           t1->right = LTTV_TREE_NODE;
1304           t1->r_child.t = t3;
1305           not = 0;
1306         }
1307         g_ptr_array_add( tree_stack,(gpointer) t1 );
1308         break;
1309
1310       case ')':   /* end of parenthesis */
1311       case ']':
1312       case '}':
1313
1314         p_nesting--;      /* decrementing parenthesis nesting value */
1315         if(p_nesting<0 || tree_stack->len<2) {
1316           g_warning("Wrong filtering options, the string\n\"%s\"\n\
1317                      is not valid due to parenthesis incorrect use",filter->expression);
1318           return FALSE;
1319         }
1320
1321         /* there must at least be the root tree left in the array */
1322         g_assert(tree_stack->len>0);
1323
1324         t1 = g_ptr_array_index(tree_stack,tree_stack->len-1);
1325         while(t1->right != LTTV_TREE_IDLE) {
1326            t1 = t1->r_child.t;
1327         }
1328         if(not) { // add not operator to tree
1329           g_print("ici");
1330           t3 = lttv_filter_tree_new();
1331           t3->node = LTTV_LOGICAL_NOT;
1332           t1->right = LTTV_TREE_NODE;
1333           t1->r_child.t = t3;
1334           t1 = t3;
1335           not = 0;
1336         }
1337         if(subtree != NULL) {   /* append subtree to current tree */
1338           t1->right = LTTV_TREE_NODE;
1339           t1->r_child.t = subtree;
1340           subtree = g_ptr_array_index(tree_stack,tree_stack->len-1);
1341           g_ptr_array_remove_index(tree_stack,tree_stack->len-1);
1342         } else {    /* assign subtree as current tree */
1343           lttv_simple_expression_assign_value(a_simple_expression,g_string_free(a_field_component,FALSE));
1344           a_field_component = g_string_new("");
1345           t1->right = LTTV_TREE_LEAF;
1346           t1->r_child.leaf = a_simple_expression;
1347           a_simple_expression = lttv_simple_expression_new();
1348           subtree = g_ptr_array_remove_index(tree_stack,tree_stack->len-1);
1349         }
1350         break;
1351
1352       /*
1353        *        mathematic operators
1354        */
1355       case '<':   /* lower, lower or equal */
1356
1357         g_ptr_array_add( a_field_path,(gpointer) a_field_component );
1358         lttv_simple_expression_assign_field(a_field_path,a_simple_expression);
1359         a_field_component = g_string_new("");
1360         if(filter->expression[i+1] == '=') { /* <= */
1361           i++;
1362           lttv_simple_expression_assign_operator(a_simple_expression,LTTV_FIELD_LE);
1363         } else lttv_simple_expression_assign_operator(a_simple_expression,LTTV_FIELD_LT);
1364        break;
1365
1366       case '>':   /* higher, higher or equal */
1367
1368         g_ptr_array_add( a_field_path,(gpointer) a_field_component );
1369         lttv_simple_expression_assign_field(a_field_path,a_simple_expression);
1370         a_field_component = g_string_new("");
1371         if(filter->expression[i+1] == '=') {  /* >= */
1372           i++;
1373           lttv_simple_expression_assign_operator(a_simple_expression,LTTV_FIELD_GE);
1374         } else lttv_simple_expression_assign_operator(a_simple_expression,LTTV_FIELD_GT);
1375        break;
1376
1377       case '=':   /* equal */
1378
1379         g_ptr_array_add( a_field_path,(gpointer) a_field_component );
1380         lttv_simple_expression_assign_field(a_field_path,a_simple_expression);
1381         a_field_component = g_string_new("");
1382         lttv_simple_expression_assign_operator(a_simple_expression,LTTV_FIELD_EQ);
1383         break;
1384
1385       /*
1386        *  Field concatening caracter
1387        */
1388       case '.':   /* dot */
1389
1390         /*
1391          * divide field expression into elements
1392          * in a_field_path array.
1393          *
1394          * A dot can also be present in double values
1395          */
1396         if(a_simple_expression->field == LTTV_FILTER_UNDEFINED) {
1397           g_ptr_array_add( a_field_path,(gpointer) a_field_component );
1398           a_field_component = g_string_new("");
1399         }
1400         break;
1401       case ' ':   /* ignore */
1402       case '\n':  /* ignore */
1403         break;
1404       default:    /* concatening current string */
1405         g_string_append_c(a_field_component,filter->expression[i]);
1406     }
1407   }
1408
1409   /*
1410    * Preliminary check to see
1411    * if tree was constructed correctly
1412    */
1413   if( p_nesting>0 ) {
1414     g_warning("Wrong filtering options, the string\n\"%s\"\n\
1415         is not valid due to parenthesis incorrect use",filter->expression);
1416     return FALSE;
1417   }
1418
1419   if(tree_stack->len != 1) /* only root tree should remain */
1420     return FALSE;
1421
1422   /*
1423    *  processing last element of expression
1424    */
1425   t1 = g_ptr_array_index(tree_stack,tree_stack->len-1);
1426   while(t1->right != LTTV_TREE_IDLE) {
1427     g_assert(t1->right == LTTV_TREE_NODE);
1428     t1 = t1->r_child.t;
1429   }
1430   if(not) { // add not operator to tree
1431      t3 = lttv_filter_tree_new();
1432      t3->node = LTTV_LOGICAL_NOT;
1433      t1->right = LTTV_TREE_NODE;
1434      t1->r_child.t = t3;
1435      t1 = t3;
1436      not = 0;
1437   }
1438   if(subtree != NULL) {  /* add the subtree */
1439     t1->right = LTTV_TREE_NODE;
1440     t1->r_child.t = subtree;
1441     subtree = NULL;
1442   } else {  /* add a leaf */
1443     lttv_simple_expression_assign_value(a_simple_expression,g_string_free(a_field_component,FALSE));
1444     a_field_component = NULL;
1445     t1->right = LTTV_TREE_LEAF;
1446     t1->r_child.leaf = a_simple_expression;
1447     a_simple_expression = NULL;
1448   }
1449
1450
1451   /* free the pointer array */
1452   g_assert(a_field_path->len == 0);
1453   g_ptr_array_free(a_field_path,TRUE);
1454
1455   /* free the tree stack -- but keep the root tree */
1456   filter->head = g_ptr_array_remove_index(tree_stack,0);
1457   g_ptr_array_free(tree_stack,TRUE);
1458
1459   /* free the field buffer if allocated */
1460   if(a_field_component != NULL) g_string_free(a_field_component,TRUE);
1461
1462   /* free the simple expression buffer if allocated */
1463   if(a_simple_expression != NULL) lttv_simple_expression_destroy(a_simple_expression);
1464
1465   g_assert(filter->head != NULL); /* tree should exist */
1466   g_assert(subtree == NULL); /* remaining subtree should be included in main tree */
1467
1468 #ifdef TEST
1469   gettimeofday(&endtime, NULL);
1470
1471   /* Calcul du temps de l'algorithme */
1472   double time1 = starttime.tv_sec + (starttime.tv_usec/1000000.0);
1473   double time2 = endtime.tv_sec + (endtime.tv_usec/1000000.0);
1474 // g_print("Tree build took %.10f ms for strlen of %i\n",(time2-time1)*1000,strlen(filter->expression));
1475   g_print("%.10f %i\n",(time2-time1)*1000,strlen(filter->expression));
1476 #endif
1477
1478   /* debug */
1479   g_print("+++++++++++++++ BEGIN PRINT ++++++++++++++++\n");
1480   lttv_print_tree(filter->head,0) ;
1481   g_print("+++++++++++++++ END PRINT ++++++++++++++++++\n");
1482
1483   /* success */
1484   return TRUE;
1485
1486 }
1487
1488 /**
1489  *  @fn void lttv_filter_destroy(LttvFilter*)
1490  *
1491  *  Destroy the current LttvFilter
1492  *  @param filter pointer to the current LttvFilter
1493  */
1494 void
1495 lttv_filter_destroy(LttvFilter* filter) {
1496
1497         if(!filter) return;
1498
1499         if(filter->expression)
1500           g_free(filter->expression);
1501         if(filter->head)
1502           lttv_filter_tree_destroy(filter->head);
1503   g_free(filter);
1504
1505 }
1506
1507 /**
1508  *  @fn LttvFilterTree* lttv_filter_tree_new()
1509  *
1510  *  Assign a new tree for the current expression
1511  *  or sub expression
1512  *  @return pointer of LttvFilterTree
1513  */
1514 LttvFilterTree*
1515 lttv_filter_tree_new() {
1516   LttvFilterTree* tree;
1517
1518   tree = g_new(LttvFilterTree,1);
1519   tree->node = 0; //g_new(lttv_expression,1);
1520   tree->left = LTTV_TREE_IDLE;
1521   tree->right = LTTV_TREE_IDLE;
1522   tree->r_child.t = NULL;
1523   tree->l_child.t = NULL;
1524
1525   return tree;
1526 }
1527
1528 /**
1529  *  @fn void lttv_filter_append_expression(LttvFilter*,char*)
1530  *
1531  *  Append a new expression to the expression
1532  *  defined in the current filter
1533  *  @param filter pointer to the current LttvFilter
1534  *  @param expression string that must be appended
1535  *  @return Success/Failure of operation
1536  */
1537 gboolean
1538 lttv_filter_append_expression(LttvFilter* filter, const char *expression) {
1539
1540   if(expression == NULL) return FALSE;
1541   if(filter == NULL) return FALSE;
1542   if(expression[0] == '\0') return FALSE;  /* Empty expression */
1543
1544   GString* s = g_string_new("");
1545   if(filter->expression != NULL) {
1546     g_string_append(s,filter->expression);
1547     g_string_append_c(s,'&');
1548   }
1549   g_string_append(s,expression);
1550
1551   g_free(filter->expression);
1552   filter->expression = g_string_free(s,FALSE);
1553
1554   /* TRUE if construction of tree proceeded without errors */
1555   return lttv_filter_update(filter);
1556
1557 }
1558
1559 /**
1560  *  @fn void lttv_filter_clear_expression(LttvFilter*)
1561  *
1562  *  Clear the filter expression from the
1563  *  current filter and sets its pointer to NULL
1564  *  @param filter pointer to the current LttvFilter
1565  */
1566 void
1567 lttv_filter_clear_expression(LttvFilter* filter) {
1568
1569   if(filter->expression != NULL) {
1570     g_free(filter->expression);
1571     filter->expression = NULL;
1572   }
1573
1574 }
1575
1576 /**
1577  *  @fn void lttv_filter_tree_destroy(LttvFilterTree*)
1578  *
1579  *  Destroys the tree and his sub-trees
1580  *  @param tree Tree which must be destroyed
1581  */
1582 void
1583 lttv_filter_tree_destroy(LttvFilterTree* tree) {
1584
1585   if(tree == NULL) return;
1586
1587   if(tree->left == LTTV_TREE_LEAF) lttv_simple_expression_destroy(tree->l_child.leaf);
1588   else if(tree->left == LTTV_TREE_NODE) lttv_filter_tree_destroy(tree->l_child.t);
1589
1590   if(tree->right == LTTV_TREE_LEAF) lttv_simple_expression_destroy(tree->r_child.leaf);
1591   else if(tree->right == LTTV_TREE_NODE) lttv_filter_tree_destroy(tree->r_child.t);
1592
1593 //  g_free(tree->node);
1594   g_free(tree);
1595 }
1596
1597 /**
1598  *  Global parsing function for the current
1599  *  LttvFilterTree
1600  *  @param t pointer to the current LttvFilterTree
1601  *  @param event current LttEvent, NULL if not used
1602  *  @param tracefile current LttTracefile, NULL if not used
1603  *  @param trace current LttTrace, NULL if not used
1604  *  @param state current LttvProcessState, NULL if not used
1605  *  @param context current LttvTracefileContext, NULL if not used
1606  *  @return response of filter
1607  */
1608 gboolean
1609 lttv_filter_tree_parse(
1610         const LttvFilterTree* t,
1611         const LttEvent* event,
1612         const LttTracefile* tracefile,
1613         const LttTrace* trace,
1614         const LttvProcessState* state,
1615         const LttvTracefileContext* context
1616         /*,...*/)
1617 {
1618
1619    /*
1620    *  Each tree is parsed in inorder.
1621    *  This way, it's possible to apply the left filter of the
1622    *  tree, then decide whether or not the right branch should
1623    *  be parsed depending on the linking logical operator
1624    *
1625    *  Each node consists in a
1626    *  1. logical operator
1627    *  2. left child ( node or simple expression )
1628    *  3. right child ( node or simple expression )
1629    *
1630    *  When the child is a simple expression, we must
1631    *  before all determine if the expression refers to
1632    *  a structure which is whithin observation ( not NULL ).
1633    *    -If so, the expression is evaluated.
1634    *    -If not, the result is set to TRUE since this particular
1635    *     operation does not interfere with the lttv structure
1636    *
1637    *  The result of each simple expression will directly
1638    *  affect the next branch.  This way, depending on
1639    *  the linking logical operator, the parser will decide
1640    *  to explore or not the next branch.
1641    *  1. AND OPERATOR
1642    *     -If result of left branch is 0 / FALSE
1643    *      then don't explore right branch and return 0;
1644    *     -If result of left branch is 1 / TRUE then explore
1645    *  2. OR OPERATOR
1646    *     -If result of left branch is 1 / TRUE
1647    *      then don't explore right branch and return 1;
1648    *     -If result of left branch is 0 / FALSE then explore
1649    *  3. XOR OPERATOR
1650    *     -Result of left branch will not affect exploration of
1651    *      right branch
1652    */
1653
1654   gboolean lresult = FALSE, rresult = FALSE;
1655
1656   /*
1657    * Parse left branch
1658    */
1659   if(t->left == LTTV_TREE_NODE) {
1660       lresult = lttv_filter_tree_parse(t->l_child.t,event,tracefile,trace,state,context);
1661   }
1662   else if(t->left == LTTV_TREE_LEAF) {
1663       lresult = lttv_filter_tree_parse_branch(t->l_child.leaf,event,tracefile,trace,state,context);
1664   }
1665
1666   /*
1667    * Parse linking operator
1668    * make a cutoff if possible
1669    */
1670   if((t->node & LTTV_LOGICAL_OR) && lresult == TRUE) return TRUE;
1671   if((t->node & LTTV_LOGICAL_AND) && lresult == FALSE) return FALSE;
1672
1673   /*
1674    * Parse right branch
1675    */
1676   if(t->right == LTTV_TREE_NODE) {
1677       rresult = lttv_filter_tree_parse(t->r_child.t,event,tracefile,trace,state,context);
1678   }
1679   else if(t->right == LTTV_TREE_LEAF) {
1680       rresult = lttv_filter_tree_parse_branch(t->r_child.leaf,event,tracefile,trace,state,context);
1681   }
1682
1683
1684   /*
1685    * Apply and return the
1686    * logical link between the
1687    * two operation
1688    */
1689   switch(t->node) {
1690     case LTTV_LOGICAL_OR: return (lresult | rresult);
1691     case LTTV_LOGICAL_AND: return (lresult & rresult);
1692     case LTTV_LOGICAL_NOT:
1693       return (t->left==LTTV_TREE_LEAF)?!lresult:((t->right==LTTV_TREE_LEAF)?!rresult:TRUE);
1694     case LTTV_LOGICAL_XOR: return (lresult ^ rresult);
1695     case 0: return (rresult);
1696     default:
1697       /*
1698        * This case should never be
1699        * parsed, if so, this subtree
1700        * is cancelled !
1701        */
1702       return TRUE;
1703   }
1704
1705 }
1706
1707 /**
1708  *  This function parses a particular branch of the tree
1709  *  @param se pointer to the current LttvSimpleExpression
1710  *  @param event current LttEvent, NULL if not used
1711  *  @param tracefile current LttTracefile, NULL if not used
1712  *  @param trace current LttTrace, NULL if not used
1713  *  @param state current LttvProcessState, NULL if not used
1714  *  @param context current LttvTracefileContext, NULL if not used
1715  *  @return response of filter
1716  */
1717 gboolean
1718 lttv_filter_tree_parse_branch(
1719         const LttvSimpleExpression* se,
1720         const LttEvent* event,
1721         const LttTracefile* tracefile,
1722         const LttTrace* trace,
1723         const LttvProcessState* state,
1724         const LttvTracefileContext* context) {
1725
1726     LttvFieldValue v;
1727     v = se->value;
1728     switch(se->field) {
1729         case LTTV_FILTER_TRACE_NAME:
1730             if(trace == NULL) return TRUE;
1731             else {
1732                 GQuark quark = ltt_trace_name(trace);
1733                 return se->op((gpointer)&quark,v);
1734             }
1735             break;
1736         case LTTV_FILTER_TRACEFILE_NAME:
1737             if(tracefile == NULL) return TRUE;
1738             else {
1739                 GQuark quark = ltt_tracefile_name(tracefile);
1740                 return se->op((gpointer)&quark,v);
1741             }
1742             break;
1743         case LTTV_FILTER_STATE_PID:
1744             if(state == NULL) return TRUE;
1745             else return se->op((gpointer)&state->pid,v);
1746             break;
1747         case LTTV_FILTER_STATE_PPID:
1748             if(state == NULL) return TRUE;
1749             else return se->op((gpointer)&state->ppid,v);
1750             break;
1751         case LTTV_FILTER_STATE_CT:
1752             if(state == NULL) return TRUE;
1753             else {
1754               return se->op((gpointer)&state->creation_time,v);
1755             }
1756             break;
1757         case LTTV_FILTER_STATE_IT:
1758             if(state == NULL) return TRUE;
1759             else {
1760               return se->op((gpointer)&state->insertion_time,v);
1761             }
1762             break;
1763         case LTTV_FILTER_STATE_P_NAME:
1764             /*
1765              * All 'unnamed' for the moment
1766              */
1767             if(state == NULL) return TRUE;
1768             else {
1769               GQuark quark = state->name;
1770               return se->op((gpointer)&quark,v);
1771             }
1772             break;
1773         case LTTV_FILTER_STATE_EX_MODE:
1774             if(state == NULL) return TRUE;
1775             else return se->op((gpointer)&state->state->t,v);
1776             break;
1777         case LTTV_FILTER_STATE_EX_SUBMODE:
1778             if(state == NULL) return TRUE;
1779             else return se->op((gpointer)&state->state->n,v);
1780             break;
1781         case LTTV_FILTER_STATE_P_STATUS:
1782             if(state == NULL) return TRUE;
1783             else return se->op((gpointer)&state->state->s,v);
1784             break;
1785         case LTTV_FILTER_STATE_CPU:
1786             if(context == NULL) return TRUE;
1787             else {
1788               /* FIXME: not sure of that one */
1789               GQuark quark = ((LttvTracefileState*)context)->cpu_name;
1790               return se->op((gpointer)&quark,v);
1791             }
1792             break;
1793         case LTTV_FILTER_EVENT_NAME:
1794             if(event == NULL) return TRUE;
1795             else {
1796               LttEventType* et;
1797               et = ltt_event_eventtype(event);
1798               GQuark quark = ltt_eventtype_name(et);
1799               return se->op((gpointer)&quark,v);
1800             }
1801             break;
1802
1803         case LTTV_FILTER_EVENT_CATEGORY:
1804             /*
1805              * TODO: Not yet implemented
1806              */
1807             return TRUE;
1808             break;
1809         case LTTV_FILTER_EVENT_TIME:
1810             if(event == NULL) return TRUE;
1811             else {
1812                 LttTime time = ltt_event_time(event);
1813                 return se->op((gpointer)&time,v);
1814             }
1815             break;
1816         case LTTV_FILTER_EVENT_TSC:
1817             if(event == NULL) return TRUE;
1818             else {
1819               LttCycleCount count = ltt_event_cycle_count(event);
1820               return se->op((gpointer)&count,v);
1821             }
1822             break;
1823         case LTTV_FILTER_EVENT_FIELD:
1824             /*
1825              * TODO: Use the offset to
1826              * find the dynamic field
1827              * in the event struct
1828              */
1829             return TRUE;
1830         default:
1831             /*
1832              * This case should never be
1833              * parsed, if so, the whole
1834              * filtering is cancelled
1835              */
1836             g_warning("Error while parsing the filter tree");
1837             return TRUE;
1838     }
1839
1840     /* should never get here */
1841     return TRUE;
1842
1843 }
1844
1845
1846
1847 /**
1848  *  Debug function.  Prints tree memory allocation.
1849  *  @param t the pointer to the current LttvFilterTree
1850  */
1851 void
1852 lttv_print_tree(const LttvFilterTree* t, const int count) {
1853
1854   g_print("node:%p lchild:%p rchild:%p depth:%i\n",t, //t->l_child.t,t->r_child.t);
1855           (t->left==LTTV_TREE_NODE)?t->l_child.t:NULL,
1856           (t->right==LTTV_TREE_NODE)?t->r_child.t:NULL,
1857           count);
1858   g_print("logic operator: %s\n",(t->node&1)?"OR":((t->node&2)?"AND":((t->node&4)?"NOT":((t->node&8)?"XOR":"IDLE"))));
1859   g_print("|-> left branch %p is a %s\n",t->l_child.t,(t->left==LTTV_TREE_NODE)?"NODE":((t->left==LTTV_TREE_LEAF)?"LEAF":"IDLE"));
1860   if(t->left == LTTV_TREE_LEAF) {
1861     g_print("| |-> field type number: %i\n",t->l_child.leaf->field);
1862     g_print("| |-> offset is: %i\n",t->l_child.leaf->offset);
1863     g_print("| |-> operator function is: %p\n",t->l_child.leaf->op);
1864   }
1865   g_print("|-> right branch %p is a %s\n",t->r_child.t,(t->right==LTTV_TREE_NODE)?"NODE":((t->right==LTTV_TREE_LEAF)?"LEAF":"IDLE"));
1866   if(t->right == LTTV_TREE_LEAF) {
1867     g_print("| |-> field type number: %i\n",t->r_child.leaf->field);
1868     g_print("| |-> offset is: %i\n",t->r_child.leaf->offset);
1869     g_print("| |-> operator function is: %p\n",t->r_child.leaf->op);
1870   }
1871
1872   if(t->left == LTTV_TREE_NODE) lttv_print_tree(t->l_child.t,count+1);
1873   if(t->right == LTTV_TREE_NODE) lttv_print_tree(t->r_child.t,count+1);
1874 }
1875
1876 /**
1877  *  @fn static void module_init()
1878  *
1879  *  Initializes the filter module and specific values
1880  */
1881 static void module_init()
1882 {
1883
1884 }
1885
1886 /**
1887  *  Destroys the filter module and specific values
1888  */
1889 static void module_destroy()
1890 {
1891
1892 }
1893
1894
1895 LTTV_MODULE("filter", "Filters traceset and events", \
1896     "Filters traceset and events specifically to user input", \
1897     module_init, module_destroy)
1898
1899
1900