Nilorea Library

- Main Page
- Data Structures
- Files

- File List
- Globals

All Data Structures Files Functions Variables Typedefs Macros
wildmat.c
Go to the documentation of this file.
1 /* $Revision: 1.2 $
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 ** behaviour 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
36 ** out on.
37 */
38
39 #include "wildmat.h"
40
41 #define ABORT -2
42
43 /* What character marks an inverted character class? */
44 #define NEGATE_CLASS '^'
45 /* Is "*" a common pattern? */
46 /*#define OPTIMIZE_JUST_STAR*/
47 /* Do tar(1) matching rules, which ignore a trailing slash? */
48 #undef MATCH_TAR_PATTERN
49
50
51 /*
52 ** Match text and p, return TRUE, FALSE, or ABORT.
53 */
54 static int
55 DoMatch(register const char *text, register const char *p)
56 {
57 register int last;
58 register int matched;
59 register int reverse;
60
61 for ( ; *p; text++, p++) {
62 if (*text == '\0' && *p != '*')
63 return ABORT;
64 switch (*p) {
65 case '\\':
66 /* Literal match with following character. */
67 p++;
68 /* FALLTHROUGH */
69 default:
70 if (*text != *p)
71 return FALSE;
72 continue;
73 case '?':
74 /* Match anything. */
75 continue;
76 case '*':
77 while (*++p == '*')
78 /* Consecutive stars act just like one. */
79 continue;
80 if (*p == '\0')
81 /* Trailing star matches everything. */
82 return TRUE;
83 while (*text)
84 if ((matched = DoMatch(text++, p)) != FALSE)
85 return matched;
86 return ABORT;
87 case '[':
88 reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
89 if (reverse)
90 /* Inverted character class. */
91 p++;
92 matched = FALSE;
93 if (p[1] == ']' || p[1] == '-')
94 if (*++p == *text)
95 matched = TRUE;
96 for (last = *p; *++p && *p != ']'; last = *p)
97 /* This next line requires a good C compiler. */
98 if (*p == '-' && p[1] != ']'
99 ? *text <= *++p && *text >= last : *text == *p)
100 matched = TRUE;
101 if (matched == reverse)
102 return FALSE;
103 continue;
104 }
105 }
106
107 #ifdef MATCH_TAR_PATTERN
108 if (*text == '/')
109 return TRUE;
110 #endif /* MATCH_TAR_ATTERN */
111 return *text == '\0';
112 }
113
114
115 /*
116 ** Match text and p, return TRUE, FALSE, or ABORT.
117 */
118 static int
119 DoMatchCaseInsensitive(register const char *text, register const char *p)
120 {
121 register int last;
122 register int matched;
123 register int reverse;
124
125 for ( ; *p; text++, p++) {
126 if (*text == '\0' && *p != '*')
127 return ABORT;
128 switch (*p) {
129 case '\\':
130 /* Literal match with following character. */
131 p++;
132 /* FALLTHROUGH */
133 default:
134 if (toupper(*text) != toupper(*p))
135 return FALSE;
136 continue;
137 case '?':
138 /* Match anything. */
139 continue;
140 case '*':
141 while (*++p == '*')
142 /* Consecutive stars act just like one. */
143 continue;
144 if (*p == '\0')
145 /* Trailing star matches everything. */
146 return TRUE;
147 while (*text)
148 if ((matched = DoMatchCaseInsensitive(text++, p)) != FALSE)
149 return matched;
150 return ABORT;
151 case '[':
152 reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
153 if (reverse)
154 /* Inverted character class. */
155 p++;
156 matched = FALSE;
157 if (p[1] == ']' || p[1] == '-')
158 if (toupper(*++p) == toupper(*text))
159 matched = TRUE;
160 for (last = toupper(*p); *++p && *p != ']'; last = toupper(*p))
161 /* This next line requires a good C compiler. */
162 if (*p == '-' && p[1] != ']'
163 ? toupper(*text) <= toupper(*++p) && toupper(*text) >= last : toupper(*text) == toupper(*p))
164 matched = TRUE;
165 if (matched == reverse)
166 return FALSE;
167 continue;
168 }
169 }
170
171 #ifdef MATCH_TAR_PATTERN
172 if (*text == '/')
173 return TRUE;
174 #endif /* MATCH_TAR_ATTERN */
175 return *text == '\0';
176 }
177
178
179 /*
180 ** User-level routine. Returns TRUE or FALSE.
181 */
182 int
183 wildmat(const char *text, const char *p)
184 {
185 #ifdef OPTIMIZE_JUST_STAR
186 if (p[0] == '*' && p[1] == '\0')
187 return TRUE;
188 #endif /* OPTIMIZE_JUST_STAR */
189 return DoMatch(text, p) == TRUE;
190 }
191
192 /*
193 ** User-level routine. Returns TRUE or FALSE.
194 */
195 int
196 wildmatcase(const char *text, const char *p)
197 {
198 #ifdef OPTIMIZE_JUST_STAR
199 if (p[0] == '*' && p[1] == '\0')
200 return TRUE;
201 #endif /* OPTIMIZE_JUST_STAR */
202 return DoMatchCaseInsensitive(text, p) == TRUE;
203 }