tin  2.6.1
About: TIN is a threaded NNTP and spool based UseNet newsreader.
  Fossies Dox: tin-2.6.1.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

wildmat.c
Go to the documentation of this file.
1/* @Revision: 1.9 @
2**
3** Do shell-style pattern matching for ?, \, [], and * characters.
4** Might not be robust in face of malformed patterns; e.g., "foo[a-"
5** could cause a segmentation violation. It is 8bit clean.
6**
7** Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
8** Rich $alz is now <rsalz@osf.org>.
9** April, 1991: Replaced mutually-recursive calls with in-line code
10** for the star character.
11**
12** Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
13** This can greatly speed up failing wildcard patterns. For example:
14** pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
15** text 1: -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
16** text 2: -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
17** Text 1 matches with 51 calls, while text 2 fails with 54 calls. Without
18** the ABORT code, it takes 22310 calls to fail. Ugh. The following
19** explanation is from Lars:
20** The precondition that must be fulfilled is that DoMatch will consume
21** at least one character in text. This is true if *p is neither '*' nor
22** '\0'.) The last return has ABORT instead of FALSE to avoid quadratic
23** behavior in cases like pattern "*a*b*c*d" with text "abcxxxxx". With
24** FALSE, each star-loop has to run to the end of the text; with ABORT
25** only the last one does.
26**
27** Once the control of one instance of DoMatch enters the star-loop, that
28** instance will return either TRUE or ABORT, and any calling instance
29** will therefore return immediately after (without calling recursively
30** again). In effect, only one star-loop is ever active. It would be
31** possible to modify the code to maintain this context explicitly,
32** eliminating all recursive calls at the cost of some complication and
33** loss of clarity (and the ABORT stuff seems to be unclear enough by
34** itself). I think it would be unwise to try to get this into a
35** released version unless you have a good test data base to try it out
36** on.
37*/
38
39#ifndef TIN_H
40# include "tin.h"
41#endif /* !TIN_H */
42
43#define ABORT -1
44
45/* What character marks an inverted character class? */
46#define NEGATE_CLASS '^'
47
48/* Is "*" a common pattern? */
49#define OPTIMIZE_JUST_STAR 1
50
51/* Do tar(1) matching rules, which ignore a trailing slash? */
52#undef MATCH_TAR_PATTERN
53
54/*
55 * local prototypes
56 */
57static int DoMatch(const char *text, char *p);
58
59/*
60 * Match text and p, return 1 (TRUE), 0 (FALSE), or -1 (ABORT).
61 */
62
63static int
65 const char *text,
66 char *p)
67{
68 int last;
69 int matched;
70 int reverse;
71
72 for (; *p; text++, p++) {
73 if (*text == '\0' && *p != '*')
74 return ABORT;
75 switch (*p) {
76 case '\\':
77 /* Literal match with following character. */
78 p++;
79 /* FALLTHROUGH */
80 default:
81 if (*text != *p)
82 return 0;
83 continue;
84 case '?':
85 /* Match anything. */
86 continue;
87 case '*':
88 while (*++p == '*')
89 /* Consecutive stars act just like one. */
90 continue;
91 if (*p == '\0')
92 /* Trailing star matches everything. */
93 return 1;
94 while (*text)
95 if ((matched = DoMatch(text++, p)) != 0)
96 return matched;
97 return ABORT;
98 case '[':
99 reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
100 if (reverse)
101 /* Inverted character class. */
102 p++;
103 matched = FALSE;
104 if (p[1] == ']' || p[1] == '-')
105 if (*++p == *text)
106 matched = TRUE;
107 for (last = *p; *++p && *p != ']'; last = *p)
108 /* This next line requires a good C compiler. */
109 if (*p == '-' && p[1] != ']' ? *text <= *++p && *text >= last : *text == *p)
110 matched = TRUE;
111 if (matched == reverse)
112 return 0;
113 continue;
114 }
115 }
116#ifdef MATCH_TAR_PATTERN
117 if (*text == '/')
118 return 1;
119#endif /* MATCH_TAR_ATTERN */
120 return *text == '\0';
121}
122
123
124/*
125 * User-level routine. Returns TRUE or FALSE.
126 */
127t_bool
129 const char *text,
130 char *p,
131 t_bool icase)
132{
133 char *txt;
134 t_bool ret;
135
136 /*
137 * Make sure the pattern is not NULL
138 */
139 if (p == NULL || text == NULL)
140 return FALSE;
141#ifdef OPTIMIZE_JUST_STAR
142 if (p[0] == '*' && p[1] == '\0')
143 return TRUE;
144#endif /* OPTIMIZE_JUST_STAR */
145
146 if (icase) {
147 txt = my_strdup(text);
148 str_lwr(txt);
149 str_lwr(p);
150 ret = (DoMatch(txt, p) == TRUE);
151 free(txt);
152 } else
153 ret = (DoMatch(text, p) == TRUE);
154
155 return ret;
156}
157
158
159/*
160 * User-level routine. Calculates position of a match within a line.
161 * Returns TRUE or FALSE.
162 */
163t_bool
165 const char *text,
166 char *p,
167 t_bool icase,
168 int *srch_offsets,
170{
171 char *txt, *t, *px;
172 int i, prev_offset = srch_offsets[1];
173 t_bool ret = FALSE;
174
175 if (srch_offsets_size >= 2)
176 srch_offsets[0] = srch_offsets[1] = 0;
177
178 /*
179 * Make sure the pattern is not NULL
180 */
181 if (p == NULL || text == NULL)
182 return FALSE;
183#ifdef OPTIMIZE_JUST_STAR
184 if (p[0] == '*' && p[1] == '\0') {
185 if (srch_offsets_size >= 2) {
186 srch_offsets[0] = 0;
187 srch_offsets[1] = (int) strlen(text);
188 }
189 return TRUE;
190 }
191#endif /* OPTIMIZE_JUST_STAR */
192
193 txt = my_strdup(text);
194 if (icase) {
195 str_lwr(txt);
196 str_lwr(p);
197 }
198
199 /* remove the leading '*' */
200 px = my_strdup(p + 1);
201
202 for (t = txt + prev_offset; *t; t++)
203 if ((ret = (DoMatch(t, px))) == 1) {
204 /* remove the trailing '*' */
205 px[strlen(px) - 1] = '\0';
206 for (i = (int) strlen(t); i > 0; i--) {
207 t[i] = '\0';
208 if ((ret = (DoMatch(t, px))) == 1) {
209 if (srch_offsets_size >= 2) {
210 srch_offsets[0] = (int) (t - txt);
211 srch_offsets[1] = srch_offsets[0] + i;
212 }
213 break;
214 }
215 }
216 break;
217 }
218 free(px);
219 free(txt);
220
221 return ret;
222}
unsigned t_bool
Definition: bool.h:77
#define TRUE
Definition: bool.h:74
#define FALSE
Definition: bool.h:70
void str_lwr(char *str)
Definition: string.c:291
char * my_strdup(const char *str)
Definition: string.c:139
static int srch_offsets_size
Definition: search.c:67
static int srch_offsets[6]
Definition: search.c:66
#define NEGATE_CLASS
Definition: wildmat.c:46
t_bool wildmatpos(const char *text, char *p, t_bool icase, int *srch_offsets, int srch_offsets_size)
Definition: wildmat.c:164
static int DoMatch(const char *text, char *p)
Definition: wildmat.c:64
#define ABORT
Definition: wildmat.c:43
t_bool wildmat(const char *text, char *p, t_bool icase)
Definition: wildmat.c:128