Bug Summary

File:build-analysis/../src/lib/s4/src/lib/pattern.c
Warning:line 231, column 12
Call to 'malloc' has an allocation size of 0 bytes

Annotated Source Code

1/* S4 - An XMMS2 medialib backend
2 * Copyright (C) 2009, 2010 Sivert Berg
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 */
14
15#include <string.h>
16#include <stdlib.h>
17#include <ctype.h>
18#include "s4_priv.h"
19
20/**
21 *
22 * @defgroup Pattern Pattern
23 * @ingroup S4
24 * @brief Functions to create and match glob-like patterns.
25 *
26 * Patterns consist of normal characters and the special characters
27 * '?' and '*', where ? matches against any character while
28 * * matches against any number of characters.
29 *
30 * @{
31 */
32
33/* The structure used to represent a sub-pattern.
34 * A sub-pattern is a string not containing any stars.
35 * The pattern 'a*bc*' is split into the sub-patterns
36 * 'a', 'bc' and ''
37 */
38typedef struct pattern_St {
39 char *str; /* The string to match, for string patterns '?' is replaced by '\0' */
40 int len; /* The lenght of the string */
41 struct pattern_St *next; /* The next sub-pattern */
42} pattern_t;
43
44struct s4_pattern_St {
45 int casefolded;
46 pattern_t *str_pattern;
47 pattern_t *pos_pattern;
48 pattern_t *neg_pattern;
49};
50
51/* Calculates 10^exp */
52static int
53_power (int exp)
54{
55 int ret = 1;
56
57 /* This is not entirely correct, as 10^0 = 1, but without this
58 * 0 is treated as 0 digits, while it is actually 1 digit
59 */
60 if (exp <= 0)
61 return 0;
62
63 for (; exp > 0; exp--)
64 ret *= 10;
65
66 return ret;
67}
68
69/* Returns a reversed copy of str, have to be freed */
70static char *
71_str_rev (const char *str)
72{
73 char *ret = strdup (str);
74 int len = strlen (ret);
75 int i, j, tmp;
76
77 for (i = 0, j = len - 1; i < j; i++, j--) {
78 /* Swap i and j */
79 tmp = ret[i];
80 ret[i] = ret[j];
81 ret[j] = tmp;
82 }
83
84 return ret;
85}
86
87/* Creates a numeric pattern of a string.
88 * The string is assumed to be a valid numeric pattern
89 */
90static pattern_t *
91_num_pattern_create (const char *pattern)
92{
93 int i;
94 int star;
95 char *str = strdup (pattern);
96 pattern_t *ret, *p;
97 ret = p = calloc (1, sizeof (pattern_t));
98
99 /* Runs through the string in reverse, splitting it up on stars */
100 for (star = 0, i = strlen (str) - 1; i >= 0; i--) {
101 if (str[i] == '*') {
102 str[i] = '\0';
103
104 /* Skip stars following stars */
105 if (!star) {
106 p->str = _str_rev (str + i + 1);
107 p->len = strlen (p->str);
108 p->next = calloc (1, sizeof (pattern_t));
109 p = p->next;
110 }
111 star = 1;
112 } else {
113 star = 0;
114 }
115 }
116
117 /* Save the rest of the string */
118 p->next = NULL((void*)0);
119 p->str = _str_rev (str);
120 p->len = strlen (p->str);
121
122 free (str);
123
124 return ret;
125}
126
127/* Matches the p->len first digits of num against p
128 * If num is too small or doesn't match -1 is returned
129 * otherwise num / (10^p->len) is returned
130 * (basically num with the matched digits cut off)
131 */
132static int32_t
133_match_num (pattern_t *p, int32_t num)
134{
135 int i;
136
137 /* Check if the number has enough digits */
138 if (num < _power (p->len - 1))
139 return -1;
140
141 /* Compare the first p->len of num digits against p->str */
142 for (i = 0; i < p->len; i++, num /= 10) {
143 if (p->str[i] != '?') {
144 int c = p->str[i] - '0';
145 int d = num % 10;
146 if (c != d)
147 return -1;
148 }
149 }
150
151 return num;
152}
153
154/* Searches the number for the pattern p
155 * Returns the digits after the matches pattern,
156 * or -1 if the pattern was not found.
157 */
158static int32_t
159_find_num (pattern_t *p, int32_t num)
160{
161 int32_t ret = 0;
162 for (; (ret = _match_num (p, num)) == -1 && num; num /= 10);
163
164 return ret;
165}
166
167/* Tries to match the pattern p against num
168 * Returns non-zero if it matches, 0 otherwise
169 */
170static int
171_num_pattern_match (pattern_t *p, int32_t num)
172{
173 int first = 1;
174
175 if (p == NULL((void*)0))
176 return 0;
177
178 /* Match the first n - 1 sub-patterns */
179 for (; p->next != NULL((void*)0); p = p->next) {
180 /* The first sub-pattern have to match exactly, no star infront of it */
181 if (first) {
182 num = _match_num (p, num);
183 first = 0;
184 } else {
185 num = _find_num (p, num);
186 }
187 if (num == -1)
188 return 0;
189 }
190
191 /* If there is only one sub-pattern it must match exactly */
192 if (first) {
193 return !_match_num (p, num);
194 } else if (p->len > 0) {
195 /* We drop everything except the last p->len digits */
196 for (; num >= _power (p->len); num /= 10);
197 return !_match_num (p, num);
198 } else {
199 return 1;
200 }
201}
202
203/* Makes a copy of str and saves it in the pattern structure
204 * If casefold is non-zero the string is casefolded with s4_string_casefold
205 */
206static void
207_copy_str (const char *str, int len, pattern_t *p, int casefold)
208{
209 GString *g_str = g_string_new ("");
210
211 if (casefold) {
5
←
Assuming 'casefold' is 0
→
6
←
Taking false branch
→
212 int prev, i;
213
214 for (i = prev = 0; i <= len; i++) {
215 if (i == len || str[i] == '\0') {
216 if (i > prev) {
217 char *c = s4_string_casefold (str + prev);
218 g_string_append (g_str, c);
219 g_free (c);
220 }
221 if (i < len)
222 g_string_append_c (g_str, '\0')g_string_append_c_inline (g_str, '\0');
223 prev = i + 1;
224 }
225 }
226
227 p->len = g_str->len;
228 p->str = malloc (p->len);
229 memcpy (p->str, g_str->str, p->len);
230 } else {
231 p->str = malloc (len);
7
←
Call to 'malloc' has an allocation size of 0 bytes
232 memcpy (p->str, str, len);
233 p->len = len;
234 }
235
236 g_string_free (g_str, TRUE(!(0)));
237}
238
239/* Creates a string pattern.
240 * If casefold is non-zero, the pattern will match against casefolded strings
241 */
242static pattern_t *
243_str_pattern_create (const char *pattern, int casefold)
244{
245 int i, prev, star;
246 char *str = strdup (pattern);
247 pattern_t *ret, *p;
248 ret = p = calloc (1, sizeof (pattern_t));
249
250 /* Walk through the string, replacing '?' with '\0'
251 * and splitting it on '*'
252 */
253 for (star = prev = i = 0; str[i]; i++) {
2
←
Loop condition is false. Execution continues on line 273
→
254 if (str[i] == '?') {
255 str[i] = '\0';
256 star = 0;
257 } else if (str[i] == '*') {
258 /* Skip stars following stars */
259 if (!star) {
260 str[i] = '\0';
261 p->next = calloc (1, sizeof (pattern_t));
262 _copy_str (str + prev, i - prev, p, casefold);
263 p = p->next;
264 star = 1;
265 }
266 prev = i + 1;
267 } else {
268 star = 0;
269 }
270 }
271
272 /* Save the tail of the string */
273 p->next = NULL((void*)0);
274 _copy_str (str + prev, i - prev, p, casefold);
3
←
Passing the value 0 via 2nd parameter 'len'
→
4
←
Calling '_copy_str'
→
275
276 free (str);
277
278 return ret;
279}
280
281/* Match a pattern against a string
282 * Returns 1 if it matches, 0 otherwise
283 */
284static int
285_match_pattern (const char *str, pattern_t *p)
286{
287 int i;
288
289 for (i = 0; i < p->len; i++) {
290 if (p->str[i] != 0 && p->str[i] != str[i])
291 return 0;
292 }
293
294 return 1;
295}
296
297/* Searches the string for the pattern p
298 * Returns the index of the first place matching, or -1 if it's not found
299 */
300static int
301_find_pattern (const char *str, int len, pattern_t *p)
302{
303 int i = 0;
304 int stop = len - p->len;
305
306 for (i = 0; i <= stop && !_match_pattern (str + i, p); i++);
307
308 if (i > stop)
309 return -1;
310 return i;
311}
312
313/* Tries to match the pattern against the given string
314 * Returns non-zero if it matches, 0 otherwise
315 */
316static int
317_str_pattern_match (pattern_t *p, const char *str)
318{
319 int first = 1;
320 int len = strlen (str);
321 int i, j;
322
323 /* Match the first n - 1 subpatterns against the string */
324 for (i = 0; i < len && p->next != NULL((void*)0); p = p->next) {
325 /* The first sub-pattern must start at index 0 */
326 if (first) {
327 if (p->len > len || !_match_pattern (str, p))
328 return 0;
329 i += p->len;
330 first = 0;
331 /* The rest can start anywhere >= i */
332 } else {
333 j = _find_pattern (str + i, len - i, p);
334 if (j == -1)
335 return 0;
336 i += j + p->len;
337 }
338 }
339
340 if (first) {
341 /* If this is the first (and last) sub-pattern it must be an exact match */
342 if (p->len != len || p->next != NULL((void*)0))
343 return 0;
344 return _match_pattern (str, p);
345 } else if (p->len <= (len - i)) {
346 /* Otherwise we match the pattern against the end of the string */
347 return _match_pattern (str + len - p->len, p);
348 } else {
349 /* In case the string is too short */
350 return 0;
351 }
352}
353
354/* Checks if the string is a numerical pattern
355 * A numerical pattern is a pattern consisting
356 * of only digits, '?' and '*'
357 */
358static int
359_is_num_pattern (const char *s)
360{
361 /* Skip leading minus */
362 if (*s == '-') s++;
363
364 for (; *s; s++) {
365 if (!isdigit (*s)((*__ctype_b_loc ())[(int) ((*s))] & (unsigned short int)
_ISdigit) && *s != '?' && *s != '*')
366 return 0;
367 }
368
369 return 1;
370}
371
372/* Free a pattern structure */
373static void
374_free_pattern (pattern_t *pattern)
375{
376 pattern_t *tmp;
377 while (pattern != NULL((void*)0)) {
378 tmp = pattern;
379 pattern = pattern->next;
380
381 free (tmp->str);
382 free (tmp);
383 }
384}
385
386/**
387 * Creates a new pattern.
388 *
389 * @param pattern The string to use as the pattern
390 * @param casefold Match against both upper and lower case
391 * @return A new pattern that may be used with s4_pattern_match.
392 * Must be freed with s4_pattern_free
393 */
394s4_pattern_t *
395s4_pattern_create (const char *pattern, int casefold)
396{
397 s4_pattern_t *ret = malloc (sizeof (s4_pattern_t));
398
399 ret->casefolded = casefold;
400 ret->str_pattern = _str_pattern_create (pattern, casefold);
1
Calling '_str_pattern_create'
→
401 ret->pos_pattern = NULL((void*)0);
402 ret->neg_pattern = NULL((void*)0);
403
404 if (_is_num_pattern (pattern)) {
405 /* No minus sign - we treat it as a positive pattern */
406 if (*pattern != '-') {
407 ret->pos_pattern = _num_pattern_create (pattern);
408 }
409 /* If there is a minus sign or a ? that could match the minus sign
410 * we cut off the ? or - and create a pattern out of the rest
411 */
412 if (*pattern == '-' || *pattern == '?') {
413 ret->neg_pattern = _num_pattern_create (pattern + 1);
414 /* A star could match the minus sign */
415 } else if (*pattern == '*') {
416 ret->neg_pattern = _num_pattern_create (pattern);
417 }
418 }
419
420 return ret;
421}
422
423/**
424 * Matches a pattern against a value
425 * @param p The pattern to use
426 * @param val The value to match
427 * @return non-zero if the pattern matches the value, 0 otherwise
428 */
429int
430s4_pattern_match (const s4_pattern_t *p, const s4_val_t *val)
431{
432 int32_t i;
433 const char *str;
434
435 if (s4_val_is_str (val)) {
436 if (p->casefolded) {
437 s4_val_get_casefolded_str (val, &str);
438 return _str_pattern_match (p->str_pattern, str);
439 } else {
440 s4_val_get_str (val, &str);
441 return _str_pattern_match (p->str_pattern, str);
442 }
443 } else if (s4_val_get_int (val, &i)) {
444 if (i >= 0) {
445 return _num_pattern_match (p->pos_pattern, i);
446 } else {
447 return _num_pattern_match (p->neg_pattern, -i);
448 }
449 }
450 return 0;
451}
452
453/**
454 * Frees a pattern created with s4_pattern_create
455 * @param pattern The pattern to free
456 */
457void
458s4_pattern_free (s4_pattern_t *pattern)
459{
460 _free_pattern (pattern->str_pattern);
461 _free_pattern (pattern->pos_pattern);
462 _free_pattern (pattern->neg_pattern);
463 free (pattern);
464}
465
466/**
467 * @}
468 */