LXR linux/tools/perf/util/strfilter.c

   1#include "util.h"
   2#include "string.h"
   3#include "strfilter.h"
   4
   5/* Operators */
   6static const char *OP_and       = "&";  /* Logical AND */
   7static const char *OP_or        = "|";  /* Logical OR */
   8static 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
  13static void strfilter_node__delete(struct strfilter_node *self)
  14{
  15        if (self) {
  16                if (self->p && !is_operator(*self->p))
  17                        free((char *)self->p);
  18                strfilter_node__delete(self->l);
  19                strfilter_node__delete(self->r);
  20                free(self);
  21        }
  22}
  23
  24void strfilter__delete(struct strfilter *self)
  25{
  26        if (self) {
  27                strfilter_node__delete(self->root);
  28                free(self);
  29        }
  30}
  31
  32static 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 */
  47retry:
  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        }
  56end:
  57        *e = p;
  58        return s;
  59}
  60
  61static struct strfilter_node *strfilter_node__alloc(const char *op,
  62                                                    struct strfilter_node *l,
  63                                                    struct strfilter_node *r)
  64{
  65        struct strfilter_node *ret = zalloc(sizeof(struct strfilter_node));
  66
  67        if (ret) {
  68                ret->p = op;
  69                ret->l = l;
  70                ret->r = r;
  71        }
  72
  73        return ret;
  74}
  75
  76static 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;
 143nomem:
 144        s = NULL;
 145error:
 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 */
 155struct strfilter *strfilter__new(const char *rules, const char **err)
 156{
 157        struct strfilter *ret = zalloc(sizeof(struct strfilter));
 158        const char *ep = NULL;
 159
 160        if (ret)
 161                ret->root = strfilter_node__new(rules, &ep);
 162
 163        if (!ret || !ret->root || *ep != '\0') {
 164                if (err)
 165                        *err = ep;
 166                strfilter__delete(ret);
 167                ret = NULL;
 168        }
 169
 170        return ret;
 171}
 172
 173static bool strfilter_node__compare(struct strfilter_node *self,
 174                                    const char *str)
 175{
 176        if (!self || !self->p)
 177                return false;
 178
 179        switch (*self->p) {
 180        case '|':       /* OR */
 181                return strfilter_node__compare(self->l, str) ||
 182                        strfilter_node__compare(self->r, str);
 183        case '&':       /* AND */
 184                return strfilter_node__compare(self->l, str) &&
 185                        strfilter_node__compare(self->r, str);
 186        case '!':       /* NOT */
 187                return !strfilter_node__compare(self->r, str);
 188        default:
 189                return strglobmatch(str, self->p);
 190        }
 191}
 192
 193/* Return true if STR matches the filter rules */
 194bool strfilter__compare(struct strfilter *self, const char *str)
 195{
 196        if (!self)
 197                return false;
 198        return strfilter_node__compare(self->root, str);
 199}
 200