1 /* wildmat.h - NNTP wildmat processing functions
3 * Copyright (c) 1994-2008 Carnegie Mellon University. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
17 * 3. The name "Carnegie Mellon University" must not be used to
18 * endorse or promote products derived from this software without
19 * prior written permission. For permission or any legal
20 * details, please contact
21 * Carnegie Mellon University
22 * Center for Technology Transfer and Enterprise Creation
25 * Pittsburgh, PA 15213
26 * (412) 268-7393, fax: (412) 268-7395
27 * innovation@andrew.cmu.edu
29 * 4. Redistributions of any form whatsoever must retain the following
31 * "This product includes software developed by Computing Services
32 * at Carnegie Mellon University (http://www.cmu.edu/computing/)."
34 * CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO
35 * THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
36 * AND FITNESS, IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
37 * FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
38 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN
39 * AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
40 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
42 * $Id: wildmat.c,v 1.4 2010/01/06 17:01:47 murch Exp $
47 ** Do shell-style pattern matching for ?, \, [], and * characters.
48 ** Might not be robust in face of malformed patterns; e.g., "foo[a-"
49 ** could cause a segmentation violation. It is 8bit clean.
51 ** Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
52 ** Rich $alz is now <rsalz@osf.org>.
53 ** April, 1991: Replaced mutually-recursive calls with in-line code
54 ** for the star character.
56 ** Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
57 ** This can greatly speed up failing wildcard patterns. For example:
58 ** pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
59 ** text 1: -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
60 ** text 2: -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
61 ** Text 1 matches with 51 calls, while text 2 fails with 54 calls. Without
62 ** the ABORT code, it takes 22310 calls to fail. Ugh. The following
63 ** explanation is from Lars:
64 ** The precondition that must be fulfilled is that DoMatch will consume
65 ** at least one character in text. This is true if *p is neither '*' nor
66 ** '\0'.) The last return has ABORT instead of FALSE to avoid quadratic
67 ** behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx". With
68 ** FALSE, each star-loop has to run to the end of the text; with ABORT
69 ** only the last one does.
71 ** Once the control of one instance of DoMatch enters the star-loop, that
72 ** instance will return either TRUE or ABORT, and any calling instance
73 ** will therefore return immediately after (without calling recursively
74 ** again). In effect, only one star-loop is ever active. It would be
75 ** possible to modify the code to maintain this context explicitly,
76 ** eliminating all recursive calls at the cost of some complication and
77 ** loss of clarity (and the ABORT stuff seems to be unclear enough by
78 ** itself). I think it would be unwise to try to get this into a
79 ** released version unless you have a good test data base to try it out
83 #include <sys/types.h>
92 /* What character marks an inverted character class? */
93 #define NEGATE_CLASS '^'
94 /* Is "*" a common pattern? */
95 #define OPTIMIZE_JUST_STAR
96 /* Do tar(1) matching rules, which ignore a trailing slash? */
97 #undef MATCH_TAR_PATTERN
101 ** Match text and p, return TRUE, FALSE, or ABORT.
103 static int DoMatch(const char *text, const char *p)
109 for ( ; *p; text++, p++) {
110 if (*text == '\0' && *p != '*')
114 /* Literal match with following character. */
122 /* Match anything. */
126 /* Consecutive stars act just like one. */
129 /* Trailing star matches everything. */
132 if ((matched = DoMatch(text++, p)) != FALSE)
136 reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
138 /* Inverted character class. */
141 if (p[1] == ']' || p[1] == '-')
144 for (last = *p; *++p && *p != ']'; last = *p)
145 /* This next line requires a good C compiler. */
146 if (*p == '-' && p[1] != ']'
147 ? *text <= *++p && *text >= last : *text == *p)
149 if (matched == reverse)
155 #ifdef MATCH_TAR_PATTERN
158 #endif /* MATCH_TAR_ATTERN */
159 return *text == '\0';
164 ** User-level routine. Returns TRUE or FALSE.
166 int wildmat(const char *text, const char *p)
168 #ifdef OPTIMIZE_JUST_STAR
169 if (p[0] == '*' && p[1] == '\0')
171 #endif /* OPTIMIZE_JUST_STAR */
172 return DoMatch(text, p) == TRUE;