|
1 /* GLIB - Library of useful routines for C programming |
|
2 * Copyright (C) 1995-1997, 1999 Peter Mattis, Red Hat, Inc. |
|
3 * Portions copyright (c) 2006 Nokia Corporation. All rights reserved. |
|
4 * |
|
5 * This library is free software; you can redistribute it and/or |
|
6 * modify it under the terms of the GNU Lesser General Public |
|
7 * License as published by the Free Software Foundation; either |
|
8 * version 2 of the License, or (at your option) any later version. |
|
9 * |
|
10 * This library is distributed in the hope that it will be useful, |
|
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
|
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
|
13 * Lesser General Public License for more details. |
|
14 * |
|
15 * You should have received a copy of the GNU Lesser General Public |
|
16 * License along with this library; if not, write to the |
|
17 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, |
|
18 * Boston, MA 02111-1307, USA. |
|
19 */ |
|
20 |
|
21 #include "config.h" |
|
22 |
|
23 #include <string.h> |
|
24 |
|
25 #include "gpattern.h" |
|
26 |
|
27 #include "gmacros.h" |
|
28 #include "gmessages.h" |
|
29 #include "gmem.h" |
|
30 #include "gunicode.h" |
|
31 #include "gutils.h" |
|
32 #include "galias.h" |
|
33 |
|
34 #ifdef __SYMBIAN32__ |
|
35 #include <glib.h> |
|
36 #endif /* __SYMBIAN32__ */ |
|
37 |
|
38 /* keep enum and structure of gpattern.c and patterntest.c in sync */ |
|
39 typedef enum |
|
40 { |
|
41 G_MATCH_ALL, /* "*A?A*" */ |
|
42 G_MATCH_ALL_TAIL, /* "*A?AA" */ |
|
43 G_MATCH_HEAD, /* "AAAA*" */ |
|
44 G_MATCH_TAIL, /* "*AAAA" */ |
|
45 G_MATCH_EXACT, /* "AAAAA" */ |
|
46 G_MATCH_LAST |
|
47 } GMatchType; |
|
48 |
|
49 struct _GPatternSpec |
|
50 { |
|
51 GMatchType match_type; |
|
52 guint pattern_length; |
|
53 guint min_length; |
|
54 guint max_length; |
|
55 gchar *pattern; |
|
56 }; |
|
57 |
|
58 |
|
59 /* --- functions --- */ |
|
60 static inline gboolean |
|
61 g_pattern_ph_match (const gchar *match_pattern, |
|
62 const gchar *match_string, |
|
63 gboolean *wildcard_reached_p) |
|
64 { |
|
65 register const gchar *pattern, *string; |
|
66 register gchar ch; |
|
67 |
|
68 pattern = match_pattern; |
|
69 string = match_string; |
|
70 |
|
71 ch = *pattern; |
|
72 pattern++; |
|
73 while (ch) |
|
74 { |
|
75 switch (ch) |
|
76 { |
|
77 case '?': |
|
78 if (!*string) |
|
79 return FALSE; |
|
80 string = g_utf8_next_char (string); |
|
81 break; |
|
82 |
|
83 case '*': |
|
84 *wildcard_reached_p = TRUE; |
|
85 do |
|
86 { |
|
87 ch = *pattern; |
|
88 pattern++; |
|
89 if (ch == '?') |
|
90 { |
|
91 if (!*string) |
|
92 return FALSE; |
|
93 string = g_utf8_next_char (string); |
|
94 } |
|
95 } |
|
96 while (ch == '*' || ch == '?'); |
|
97 if (!ch) |
|
98 return TRUE; |
|
99 do |
|
100 { |
|
101 gboolean next_wildcard_reached = FALSE; |
|
102 while (ch != *string) |
|
103 { |
|
104 if (!*string) |
|
105 return FALSE; |
|
106 string = g_utf8_next_char (string); |
|
107 } |
|
108 string++; |
|
109 if (g_pattern_ph_match (pattern, string, &next_wildcard_reached)) |
|
110 return TRUE; |
|
111 if (next_wildcard_reached) |
|
112 /* the forthcoming pattern substring up to the next wildcard has |
|
113 * been matched, but a mismatch occoured for the rest of the |
|
114 * pattern, following the next wildcard. |
|
115 * there's no need to advance the current match position any |
|
116 * further if the rest pattern will not match. |
|
117 */ |
|
118 return FALSE; |
|
119 } |
|
120 while (*string); |
|
121 break; |
|
122 |
|
123 default: |
|
124 if (ch == *string) |
|
125 string++; |
|
126 else |
|
127 return FALSE; |
|
128 break; |
|
129 } |
|
130 |
|
131 ch = *pattern; |
|
132 pattern++; |
|
133 } |
|
134 |
|
135 return *string == 0; |
|
136 } |
|
137 |
|
138 EXPORT_C gboolean |
|
139 g_pattern_match (GPatternSpec *pspec, |
|
140 guint string_length, |
|
141 const gchar *string, |
|
142 const gchar *string_reversed) |
|
143 { |
|
144 g_return_val_if_fail (pspec != NULL, FALSE); |
|
145 g_return_val_if_fail (string != NULL, FALSE); |
|
146 |
|
147 if (string_length < pspec->min_length || |
|
148 string_length > pspec->max_length) |
|
149 return FALSE; |
|
150 |
|
151 switch (pspec->match_type) |
|
152 { |
|
153 gboolean dummy; |
|
154 case G_MATCH_ALL: |
|
155 return g_pattern_ph_match (pspec->pattern, string, &dummy); |
|
156 case G_MATCH_ALL_TAIL: |
|
157 if (string_reversed) |
|
158 return g_pattern_ph_match (pspec->pattern, string_reversed, &dummy); |
|
159 else |
|
160 { |
|
161 gboolean result; |
|
162 gchar *tmp; |
|
163 tmp = g_utf8_strreverse (string, string_length); |
|
164 result = g_pattern_ph_match (pspec->pattern, tmp, &dummy); |
|
165 g_free (tmp); |
|
166 return result; |
|
167 } |
|
168 case G_MATCH_HEAD: |
|
169 if (pspec->pattern_length == string_length) |
|
170 return strcmp (pspec->pattern, string) == 0; |
|
171 else if (pspec->pattern_length) |
|
172 return strncmp (pspec->pattern, string, pspec->pattern_length) == 0; |
|
173 else |
|
174 return TRUE; |
|
175 case G_MATCH_TAIL: |
|
176 if (pspec->pattern_length) |
|
177 return strcmp (pspec->pattern, string + (string_length - pspec->pattern_length)) == 0; |
|
178 else |
|
179 return TRUE; |
|
180 case G_MATCH_EXACT: |
|
181 if (pspec->pattern_length != string_length) |
|
182 return FALSE; |
|
183 else |
|
184 return strcmp (pspec->pattern, string) == 0; |
|
185 default: |
|
186 g_return_val_if_fail (pspec->match_type < G_MATCH_LAST, FALSE); |
|
187 return FALSE; |
|
188 } |
|
189 } |
|
190 |
|
191 EXPORT_C GPatternSpec* |
|
192 g_pattern_spec_new (const gchar *pattern) |
|
193 { |
|
194 GPatternSpec *pspec; |
|
195 gboolean seen_joker = FALSE, seen_wildcard = FALSE, more_wildcards = FALSE; |
|
196 gint hw_pos = -1, tw_pos = -1, hj_pos = -1, tj_pos = -1; |
|
197 gboolean follows_wildcard = FALSE; |
|
198 guint pending_jokers = 0; |
|
199 const gchar *s; |
|
200 gchar *d; |
|
201 guint i; |
|
202 |
|
203 g_return_val_if_fail (pattern != NULL, NULL); |
|
204 |
|
205 /* canonicalize pattern and collect necessary stats */ |
|
206 pspec = g_new (GPatternSpec, 1); |
|
207 pspec->pattern_length = strlen (pattern); |
|
208 pspec->min_length = 0; |
|
209 pspec->pattern = g_new (gchar, pspec->pattern_length + 1); |
|
210 d = pspec->pattern; |
|
211 for (i = 0, s = pattern; *s != 0; s++) |
|
212 { |
|
213 switch (*s) |
|
214 { |
|
215 case '*': |
|
216 if (follows_wildcard) /* compress multiple wildcards */ |
|
217 { |
|
218 pspec->pattern_length--; |
|
219 continue; |
|
220 } |
|
221 follows_wildcard = TRUE; |
|
222 if (hw_pos < 0) |
|
223 hw_pos = i; |
|
224 tw_pos = i; |
|
225 break; |
|
226 case '?': |
|
227 pending_jokers++; |
|
228 pspec->min_length++; |
|
229 pspec->max_length += 4; /* maximum UTF-8 character length */ |
|
230 continue; |
|
231 default: |
|
232 for (; pending_jokers; pending_jokers--, i++) { |
|
233 *d++ = '?'; |
|
234 if (hj_pos < 0) |
|
235 hj_pos = i; |
|
236 tj_pos = i; |
|
237 } |
|
238 follows_wildcard = FALSE; |
|
239 pspec->min_length++; |
|
240 pspec->max_length++; |
|
241 break; |
|
242 } |
|
243 *d++ = *s; |
|
244 i++; |
|
245 } |
|
246 for (; pending_jokers; pending_jokers--) { |
|
247 *d++ = '?'; |
|
248 if (hj_pos < 0) |
|
249 hj_pos = i; |
|
250 tj_pos = i; |
|
251 } |
|
252 *d++ = 0; |
|
253 seen_joker = hj_pos >= 0; |
|
254 seen_wildcard = hw_pos >= 0; |
|
255 more_wildcards = seen_wildcard && hw_pos != tw_pos; |
|
256 if (seen_wildcard) |
|
257 pspec->max_length = G_MAXUINT; |
|
258 |
|
259 /* special case sole head/tail wildcard or exact matches */ |
|
260 if (!seen_joker && !more_wildcards) |
|
261 { |
|
262 if (pspec->pattern[0] == '*') |
|
263 { |
|
264 pspec->match_type = G_MATCH_TAIL; |
|
265 memmove (pspec->pattern, pspec->pattern + 1, --pspec->pattern_length); |
|
266 pspec->pattern[pspec->pattern_length] = 0; |
|
267 return pspec; |
|
268 } |
|
269 if (pspec->pattern_length > 0 && |
|
270 pspec->pattern[pspec->pattern_length - 1] == '*') |
|
271 { |
|
272 pspec->match_type = G_MATCH_HEAD; |
|
273 pspec->pattern[--pspec->pattern_length] = 0; |
|
274 return pspec; |
|
275 } |
|
276 if (!seen_wildcard) |
|
277 { |
|
278 pspec->match_type = G_MATCH_EXACT; |
|
279 return pspec; |
|
280 } |
|
281 } |
|
282 |
|
283 /* now just need to distinguish between head or tail match start */ |
|
284 tw_pos = pspec->pattern_length - 1 - tw_pos; /* last pos to tail distance */ |
|
285 tj_pos = pspec->pattern_length - 1 - tj_pos; /* last pos to tail distance */ |
|
286 if (seen_wildcard) |
|
287 pspec->match_type = tw_pos > hw_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL; |
|
288 else /* seen_joker */ |
|
289 pspec->match_type = tj_pos > hj_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL; |
|
290 if (pspec->match_type == G_MATCH_ALL_TAIL) { |
|
291 gchar *tmp = pspec->pattern; |
|
292 pspec->pattern = g_utf8_strreverse (pspec->pattern, pspec->pattern_length); |
|
293 g_free (tmp); |
|
294 } |
|
295 return pspec; |
|
296 } |
|
297 |
|
298 EXPORT_C void |
|
299 g_pattern_spec_free (GPatternSpec *pspec) |
|
300 { |
|
301 g_return_if_fail (pspec != NULL); |
|
302 |
|
303 g_free (pspec->pattern); |
|
304 g_free (pspec); |
|
305 } |
|
306 |
|
307 EXPORT_C gboolean |
|
308 g_pattern_spec_equal (GPatternSpec *pspec1, |
|
309 GPatternSpec *pspec2) |
|
310 { |
|
311 g_return_val_if_fail (pspec1 != NULL, FALSE); |
|
312 g_return_val_if_fail (pspec2 != NULL, FALSE); |
|
313 |
|
314 return (pspec1->pattern_length == pspec2->pattern_length && |
|
315 pspec1->match_type == pspec2->match_type && |
|
316 strcmp (pspec1->pattern, pspec2->pattern) == 0); |
|
317 } |
|
318 |
|
319 EXPORT_C gboolean |
|
320 g_pattern_match_string (GPatternSpec *pspec, |
|
321 const gchar *string) |
|
322 { |
|
323 g_return_val_if_fail (pspec != NULL, FALSE); |
|
324 g_return_val_if_fail (string != NULL, FALSE); |
|
325 |
|
326 return g_pattern_match (pspec, strlen (string), string, NULL); |
|
327 } |
|
328 |
|
329 EXPORT_C gboolean |
|
330 g_pattern_match_simple (const gchar *pattern, |
|
331 const gchar *string) |
|
332 { |
|
333 GPatternSpec *pspec; |
|
334 gboolean ergo; |
|
335 |
|
336 g_return_val_if_fail (pattern != NULL, FALSE); |
|
337 g_return_val_if_fail (string != NULL, FALSE); |
|
338 |
|
339 pspec = g_pattern_spec_new (pattern); |
|
340 ergo = g_pattern_match (pspec, strlen (string), string, NULL); |
|
341 g_pattern_spec_free (pspec); |
|
342 |
|
343 return ergo; |
|
344 } |
|
345 |
|
346 #define __G_PATTERN_C__ |
|
347 #include "galiasdef.c" |