tools/perf/util/strfilter.c

   1 #include "util.h"
   2 #include "string.h"
   3 #include "strfilter.h"
   4
   5 /* Operators */
   6 static const char *OP_and       = "&";  /* Logical AND */
   7 static const char *OP_or        = "|";  /* Logical OR */
   8 static const char *OP_not       = "!";  /* Logical NOT */
   9
  10 #define is_operator(c)  ((c) == '|' || (c) == '&' || (c) == '!')
  11 #define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')')
  12
  13 static void strfilter_node__delete(struct strfilter_node *node)
  14 {
  15         if (node) {
  16                 if (node->p && !is_operator(*node->p))
  17                         free((char *)node->p);
  18                 strfilter_node__delete(node->l);
  19                 strfilter_node__delete(node->r);
  20                 free(node);
  21         }
  22 }
  23
  24 void strfilter__delete(struct strfilter *filter)
  25 {
  26         if (filter) {
  27                 strfilter_node__delete(filter->root);
  28                 free(filter);
  29         }
  30 }
  31
  32 static const char *get_token(const char *s, const char **e)
  33 {
  34         const char *p;
  35
  36         while (isspace(*s))     /* Skip spaces */
  37                 s++;
  38
  39         if (*s == '\0') {
  40                 p = s;
  41                 goto end;
  42         }
  43
  44         p = s + 1;
  45         if (!is_separator(*s)) {
  46                 /* End search */
  47 retry:
  48                 while (*p && !is_separator(*p) && !isspace(*p))
  49                         p++;
  50                 /* Escape and special case: '!' is also used in glob pattern */
  51                 if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) {
  52                         p++;
  53                         goto retry;
  54                 }
  55         }
  56 end:
  57         *e = p;
  58         return s;
  59 }
  60
  61 static struct strfilter_node *strfilter_node__alloc(const char *op,
  62                                                     struct strfilter_node *l,
  63                                                     struct strfilter_node *r)
  64 {
  65         struct strfilter_node *node = zalloc(sizeof(*node));
  66
  67         if (node) {
  68                 node->p = op;
  69                 node->l = l;
  70                 node->r = r;
  71         }
  72
  73         return node;
  74 }
  75
  76 static struct strfilter_node *strfilter_node__new(const char *s,
  77                                                   const char **ep)
  78 {
  79         struct strfilter_node root, *cur, *last_op;
  80         const char *e;
  81
  82         if (!s)
  83                 return NULL;
  84
  85         memset(&root, 0, sizeof(root));
  86         last_op = cur = &root;
  87
  88         s = get_token(s, &e);
  89         while (*s != '\0' && *s != ')') {
  90                 switch (*s) {
  91                 case '&':       /* Exchg last OP->r with AND */
  92                         if (!cur->r || !last_op->r)
  93                                 goto error;
  94                         cur = strfilter_node__alloc(OP_and, last_op->r, NULL);
  95                         if (!cur)
  96                                 goto nomem;
  97                         last_op->r = cur;
  98                         last_op = cur;
  99                         break;
 100                 case '|':       /* Exchg the root with OR */
 101                         if (!cur->r || !root.r)
 102                                 goto error;
 103                         cur = strfilter_node__alloc(OP_or, root.r, NULL);
 104                         if (!cur)
 105                                 goto nomem;
 106                         root.r = cur;
 107                         last_op = cur;
 108                         break;
 109                 case '!':       /* Add NOT as a leaf node */
 110                         if (cur->r)
 111                                 goto error;
 112                         cur->r = strfilter_node__alloc(OP_not, NULL, NULL);
 113                         if (!cur->r)
 114                                 goto nomem;
 115                         cur = cur->r;
 116                         break;
 117                 case '(':       /* Recursively parses inside the parenthesis */
 118                         if (cur->r)
 119                                 goto error;
 120                         cur->r = strfilter_node__new(s + 1, &s);
 121                         if (!s)
 122                                 goto nomem;
 123                         if (!cur->r || *s != ')')
 124                                 goto error;
 125                         e = s + 1;
 126                         break;
 127                 default:
 128                         if (cur->r)
 129                                 goto error;
 130                         cur->r = strfilter_node__alloc(NULL, NULL, NULL);
 131                         if (!cur->r)
 132                                 goto nomem;
 133                         cur->r->p = strndup(s, e - s);
 134                         if (!cur->r->p)
 135                                 goto nomem;
 136                 }
 137                 s = get_token(e, &e);
 138         }
 139         if (!cur->r)
 140                 goto error;
 141         *ep = s;
 142         return root.r;
 143 nomem:
 144         s = NULL;
 145 error:
 146         *ep = s;
 147         strfilter_node__delete(root.r);
 148         return NULL;
 149 }
 150
 151 /*
 152  * Parse filter rule and return new strfilter.
 153  * Return NULL if fail, and *ep == NULL if memory allocation failed.
 154  */
 155 struct strfilter *strfilter__new(const char *rules, const char **err)
 156 {
 157         struct strfilter *filter = zalloc(sizeof(*filter));
 158         const char *ep = NULL;
 159
 160         if (filter)
 161                 filter->root = strfilter_node__new(rules, &ep);
 162
 163         if (!filter || !filter->root || *ep != '\0') {
 164                 if (err)
 165                         *err = ep;
 166                 strfilter__delete(filter);
 167                 filter = NULL;
 168         }
 169
 170         return filter;
 171 }
 172
 173 static bool strfilter_node__compare(struct strfilter_node *node,
 174                                     const char *str)
 175 {
 176         if (!node || !node->p)
 177                 return false;
 178
 179         switch (*node->p) {
 180         case '|':       /* OR */
 181                 return strfilter_node__compare(node->l, str) ||
 182                         strfilter_node__compare(node->r, str);
 183         case '&':       /* AND */
 184                 return strfilter_node__compare(node->l, str) &&
 185                         strfilter_node__compare(node->r, str);
 186         case '!':       /* NOT */
 187                 return !strfilter_node__compare(node->r, str);
 188         default:
 189                 return strglobmatch(str, node->p);
 190         }
 191 }
 192
 193 /* Return true if STR matches the filter rules */
 194 bool strfilter__compare(struct strfilter *filter, const char *str)
 195 {
 196         if (!filter)
 197                 return false;
 198         return strfilter_node__compare(filter->root, str);
 199 }