~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/tools/perf/util/strfilter.c

Version: ~ [ linux-6.0-rc6 ] ~ [ linux-5.19.10 ] ~ [ linux-5.18.19 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.69 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.144 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.214 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.259 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.294 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.329 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.302 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 // SPDX-License-Identifier: GPL-2.0
  2 #include "util.h"
  3 #include "string2.h"
  4 #include "strfilter.h"
  5 
  6 #include <errno.h>
  7 #include "sane_ctype.h"
  8 
  9 /* Operators */
 10 static const char *OP_and       = "&";  /* Logical AND */
 11 static const char *OP_or        = "|";  /* Logical OR */
 12 static const char *OP_not       = "!";  /* Logical NOT */
 13 
 14 #define is_operator(c)  ((c) == '|' || (c) == '&' || (c) == '!')
 15 #define is_separator(c) (is_operator(c) || (c) == '(' || (c) == ')')
 16 
 17 static void strfilter_node__delete(struct strfilter_node *node)
 18 {
 19         if (node) {
 20                 if (node->p && !is_operator(*node->p))
 21                         zfree((char **)&node->p);
 22                 strfilter_node__delete(node->l);
 23                 strfilter_node__delete(node->r);
 24                 free(node);
 25         }
 26 }
 27 
 28 void strfilter__delete(struct strfilter *filter)
 29 {
 30         if (filter) {
 31                 strfilter_node__delete(filter->root);
 32                 free(filter);
 33         }
 34 }
 35 
 36 static const char *get_token(const char *s, const char **e)
 37 {
 38         const char *p;
 39 
 40         while (isspace(*s))     /* Skip spaces */
 41                 s++;
 42 
 43         if (*s == '\0') {
 44                 p = s;
 45                 goto end;
 46         }
 47 
 48         p = s + 1;
 49         if (!is_separator(*s)) {
 50                 /* End search */
 51 retry:
 52                 while (*p && !is_separator(*p) && !isspace(*p))
 53                         p++;
 54                 /* Escape and special case: '!' is also used in glob pattern */
 55                 if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) {
 56                         p++;
 57                         goto retry;
 58                 }
 59         }
 60 end:
 61         *e = p;
 62         return s;
 63 }
 64 
 65 static struct strfilter_node *strfilter_node__alloc(const char *op,
 66                                                     struct strfilter_node *l,
 67                                                     struct strfilter_node *r)
 68 {
 69         struct strfilter_node *node = zalloc(sizeof(*node));
 70 
 71         if (node) {
 72                 node->p = op;
 73                 node->l = l;
 74                 node->r = r;
 75         }
 76 
 77         return node;
 78 }
 79 
 80 static struct strfilter_node *strfilter_node__new(const char *s,
 81                                                   const char **ep)
 82 {
 83         struct strfilter_node root, *cur, *last_op;
 84         const char *e;
 85 
 86         if (!s)
 87                 return NULL;
 88 
 89         memset(&root, 0, sizeof(root));
 90         last_op = cur = &root;
 91 
 92         s = get_token(s, &e);
 93         while (*s != '\0' && *s != ')') {
 94                 switch (*s) {
 95                 case '&':       /* Exchg last OP->r with AND */
 96                         if (!cur->r || !last_op->r)
 97                                 goto error;
 98                         cur = strfilter_node__alloc(OP_and, last_op->r, NULL);
 99                         if (!cur)
100                                 goto nomem;
101                         last_op->r = cur;
102                         last_op = cur;
103                         break;
104                 case '|':       /* Exchg the root with OR */
105                         if (!cur->r || !root.r)
106                                 goto error;
107                         cur = strfilter_node__alloc(OP_or, root.r, NULL);
108                         if (!cur)
109                                 goto nomem;
110                         root.r = cur;
111                         last_op = cur;
112                         break;
113                 case '!':       /* Add NOT as a leaf node */
114                         if (cur->r)
115                                 goto error;
116                         cur->r = strfilter_node__alloc(OP_not, NULL, NULL);
117                         if (!cur->r)
118                                 goto nomem;
119                         cur = cur->r;
120                         break;
121                 case '(':       /* Recursively parses inside the parenthesis */
122                         if (cur->r)
123                                 goto error;
124                         cur->r = strfilter_node__new(s + 1, &s);
125                         if (!s)
126                                 goto nomem;
127                         if (!cur->r || *s != ')')
128                                 goto error;
129                         e = s + 1;
130                         break;
131                 default:
132                         if (cur->r)
133                                 goto error;
134                         cur->r = strfilter_node__alloc(NULL, NULL, NULL);
135                         if (!cur->r)
136                                 goto nomem;
137                         cur->r->p = strndup(s, e - s);
138                         if (!cur->r->p)
139                                 goto nomem;
140                 }
141                 s = get_token(e, &e);
142         }
143         if (!cur->r)
144                 goto error;
145         *ep = s;
146         return root.r;
147 nomem:
148         s = NULL;
149 error:
150         *ep = s;
151         strfilter_node__delete(root.r);
152         return NULL;
153 }
154 
155 /*
156  * Parse filter rule and return new strfilter.
157  * Return NULL if fail, and *ep == NULL if memory allocation failed.
158  */
159 struct strfilter *strfilter__new(const char *rules, const char **err)
160 {
161         struct strfilter *filter = zalloc(sizeof(*filter));
162         const char *ep = NULL;
163 
164         if (filter)
165                 filter->root = strfilter_node__new(rules, &ep);
166 
167         if (!filter || !filter->root || *ep != '\0') {
168                 if (err)
169                         *err = ep;
170                 strfilter__delete(filter);
171                 filter = NULL;
172         }
173 
174         return filter;
175 }
176 
177 static int strfilter__append(struct strfilter *filter, bool _or,
178                              const char *rules, const char **err)
179 {
180         struct strfilter_node *right, *root;
181         const char *ep = NULL;
182 
183         if (!filter || !rules)
184                 return -EINVAL;
185 
186         right = strfilter_node__new(rules, &ep);
187         if (!right || *ep != '\0') {
188                 if (err)
189                         *err = ep;
190                 goto error;
191         }
192         root = strfilter_node__alloc(_or ? OP_or : OP_and, filter->root, right);
193         if (!root) {
194                 ep = NULL;
195                 goto error;
196         }
197 
198         filter->root = root;
199         return 0;
200 
201 error:
202         strfilter_node__delete(right);
203         return ep ? -EINVAL : -ENOMEM;
204 }
205 
206 int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
207 {
208         return strfilter__append(filter, true, rules, err);
209 }
210 
211 int strfilter__and(struct strfilter *filter, const char *rules,
212                    const char **err)
213 {
214         return strfilter__append(filter, false, rules, err);
215 }
216 
217 static bool strfilter_node__compare(struct strfilter_node *node,
218                                     const char *str)
219 {
220         if (!node || !node->p)
221                 return false;
222 
223         switch (*node->p) {
224         case '|':       /* OR */
225                 return strfilter_node__compare(node->l, str) ||
226                         strfilter_node__compare(node->r, str);
227         case '&':       /* AND */
228                 return strfilter_node__compare(node->l, str) &&
229                         strfilter_node__compare(node->r, str);
230         case '!':       /* NOT */
231                 return !strfilter_node__compare(node->r, str);
232         default:
233                 return strglobmatch(str, node->p);
234         }
235 }
236 
237 /* Return true if STR matches the filter rules */
238 bool strfilter__compare(struct strfilter *filter, const char *str)
239 {
240         if (!filter)
241                 return false;
242         return strfilter_node__compare(filter->root, str);
243 }
244 
245 static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
246 
247 /* sprint node in parenthesis if needed */
248 static int strfilter_node__sprint_pt(struct strfilter_node *node, char *buf)
249 {
250         int len;
251         int pt = node->r ? 2 : 0;       /* don't need to check node->l */
252 
253         if (buf && pt)
254                 *buf++ = '(';
255         len = strfilter_node__sprint(node, buf);
256         if (len < 0)
257                 return len;
258         if (buf && pt)
259                 *(buf + len) = ')';
260         return len + pt;
261 }
262 
263 static int strfilter_node__sprint(struct strfilter_node *node, char *buf)
264 {
265         int len = 0, rlen;
266 
267         if (!node || !node->p)
268                 return -EINVAL;
269 
270         switch (*node->p) {
271         case '|':
272         case '&':
273                 len = strfilter_node__sprint_pt(node->l, buf);
274                 if (len < 0)
275                         return len;
276                 __fallthrough;
277         case '!':
278                 if (buf) {
279                         *(buf + len++) = *node->p;
280                         buf += len;
281                 } else
282                         len++;
283                 rlen = strfilter_node__sprint_pt(node->r, buf);
284                 if (rlen < 0)
285                         return rlen;
286                 len += rlen;
287                 break;
288         default:
289                 len = strlen(node->p);
290                 if (buf)
291                         strcpy(buf, node->p);
292         }
293 
294         return len;
295 }
296 
297 char *strfilter__string(struct strfilter *filter)
298 {
299         int len;
300         char *ret = NULL;
301 
302         len = strfilter_node__sprint(filter->root, NULL);
303         if (len < 0)
304                 return NULL;
305 
306         ret = malloc(len + 1);
307         if (ret)
308                 strfilter_node__sprint(filter->root, ret);
309 
310         return ret;
311 }
312 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp