~ [ 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 #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                         zfree((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 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 
197 error:
198         strfilter_node__delete(right);
199         return ep ? -EINVAL : -ENOMEM;
200 }
201 
202 int strfilter__or(struct strfilter *filter, const char *rules, const char **err)
203 {
204         return strfilter__append(filter, true, rules, err);
205 }
206 
207 int strfilter__and(struct strfilter *filter, const char *rules,
208                    const char **err)
209 {
210         return strfilter__append(filter, false, rules, err);
211 }
212 
213 static 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 */
234 bool 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 
241 static int strfilter_node__sprint(struct strfilter_node *node, char *buf);
242 
243 /* sprint node in parenthesis if needed */
244 static 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 
259 static 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 
292 char *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 

~ [ 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