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 *node)
  14{
  15        if (node) {
  16                if (node->p && !is_operator(*node->p))
  17                        zfree((char **)&node->p);
  18                strfilter_node__delete(node->l);
  19                strfilter_node__delete(node->r);
  20                free(node);
  21        }
  22}
  23
  24void strfilter__delete(struct strfilter *filter)
  25{
  26        if (filter) {
  27                strfilter_node__delete(filter->root);
  28                free(filter);
  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 *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
  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 *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
 173static int strfilter__append(struct strfilter *filter, bool _or,
 174                             const char *rules, const char **err)
 175{
 176        struct strfilter_node *right, *root;
 177        const char *ep = NULL;
 178
 179        if (!filter || !rules)
 180                return -EINVAL;
 181
 182        right = strfilter_node__new(rules, &ep);
 183        if (!right || *ep != '\0') {
 184                if (err)
 185                        *err = ep;
 186                goto error;
 187        }
 188        root = strfilter_node__alloc(_or ? OP_or : OP_and, filter->root, right);
 189        if (!root) {
 190                ep = NULL;
 191                goto error;
 192        }
 193
 194        filter->root = root;
 195        return 0;
 196
 197error:
 198        strfilter_node__delete(right);
 199        return ep ? -EINVAL : -ENOMEM;
 200}
 201
 202int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
 203{
 204        return strfilter__append(filter, true, rules, err);
 205}
 206
 207int strfilter__and(struct strfilter *filter, const char *rules,
 208                   const char **err)
 209{
 210        return strfilter__append(filter, false, rules, err);
 211}
 212
 213static bool strfilter_node__compare(struct strfilter_node *node,
 214                                    const char *str)
 215{
 216        if (!node || !node->p)
 217                return false;
 218
 219        switch (*node->p) {
 220        case '|':       /* OR */
 221                return strfilter_node__compare(node->l, str) ||
 222                        strfilter_node__compare(node->r, str);
 223        case '&':       /* AND */
 224                return strfilter_node__compare(node->l, str) &&
 225                        strfilter_node__compare(node->r, str);
 226        case '!':       /* NOT */
 227                return !strfilter_node__compare(node->r, str);
 228        default:
 229                return strglobmatch(str, node->p);
 230        }
 231}
 232
 233/* Return true if STR matches the filter rules */
 234bool strfilter__compare(struct strfilter *filter, const char *str)
 235{
 236        if (!filter)
 237                return false;
 238        return strfilter_node__compare(filter->root, str);
 239}
 240
 241static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
 242
 243/* sprint node in parenthesis if needed */
 244static int strfilter_node__sprint_pt(struct strfilter_node *node, char *buf)
 245{
 246        int len;
 247        int pt = node->r ? 2 : 0;       /* don't need to check node->l */
 248
 249        if (buf && pt)
 250                *buf++ = '(';
 251        len = strfilter_node__sprint(node, buf);
 252        if (len < 0)
 253                return len;
 254        if (buf && pt)
 255                *(buf + len) = ')';
 256        return len + pt;
 257}
 258
 259static int strfilter_node__sprint(struct strfilter_node *node, char *buf)
 260{
 261        int len = 0, rlen;
 262
 263        if (!node || !node->p)
 264                return -EINVAL;
 265
 266        switch (*node->p) {
 267        case '|':
 268        case '&':
 269                len = strfilter_node__sprint_pt(node->l, buf);
 270                if (len < 0)
 271                        return len;
 272        case '!':
 273                if (buf) {
 274                        *(buf + len++) = *node->p;
 275                        buf += len;
 276                } else
 277                        len++;
 278                rlen = strfilter_node__sprint_pt(node->r, buf);
 279                if (rlen < 0)
 280                        return rlen;
 281                len += rlen;
 282                break;
 283        default:
 284                len = strlen(node->p);
 285                if (buf)
 286                        strcpy(buf, node->p);
 287        }
 288
 289        return len;
 290}
 291
 292char *strfilter__string(struct strfilter *filter)
 293{
 294        int len;
 295        char *ret = NULL;
 296
 297        len = strfilter_node__sprint(filter->root, NULL);
 298        if (len < 0)
 299                return NULL;
 300
 301        ret = malloc(len + 1);
 302        if (ret)
 303                strfilter_node__sprint(filter->root, ret);
 304
 305        return ret;
 306}
 307