"Fossies" - the Fresh Open Source Software Archive 
Member "leafnode-1.12.0/wildmat.c" (30 Jan 2009, 5133 Bytes) of package /linux/misc/leafnode-1.12.0.tar.xz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "wildmat.c" see the
Fossies "Dox" file reference documentation.
1 #include "leafnode.h"
2
3 #ifdef WITH_DMALLOC
4 #include <dmalloc.h>
5 #endif
6
7 /**************************************************************************/
8 /*
9 * The following routines comprise the wildmat routine. Written by
10 * Rich $alz, taken vom INN 2.2.2
11 */
12
13 /*
14 **
15 ** Do shell-style pattern matching for ?, \, [], and * characters.
16 ** Might not be robust in face of malformed patterns; e.g., "foo[a-"
17 ** could cause a segmentation violation. It is 8bit clean.
18 **
19 ** Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
20 ** Rich $alz is now <rsalz@osf.org>.
21 ** April, 1991: Replaced mutually-recursive calls with in-line code
22 ** for the star character.
23 **
24 ** Special thanks to Lars Mathiesen <thorinn@diku.dk> for the ABORT code.
25 ** This can greatly speed up failing wildcard patterns. For example:
26 ** pattern: -*-*-*-*-*-*-12-*-*-*-m-*-*-*
27 ** text 1: -adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1
28 ** text 2: -adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1
29 ** Text 1 matches with 51 calls, while text 2 fails with 54 calls. Without
30 ** the ABORT code, it takes 22310 calls to fail. Ugh. The following
31 ** explanation is from Lars:
32 ** The precondition that must be fulfilled is that DoMatch will consume
33 ** at least one character in text. This is true if *p is neither '*' nor
34 ** '\0'.) The last return has ABORT instead of FALSE to avoid quadratic
35 ** behaviour in cases like pattern "*a*b*c*d" with text "abcxxxxx". With
36 ** FALSE, each star-loop has to run to the end of the text; with ABORT
37 ** only the last one does.
38 **
39 ** Once the control of one instance of DoMatch enters the star-loop, that
40 ** instance will return either TRUE or ABORT, and any calling instance
41 ** will therefore return immediately after (without calling recursively
42 ** again). In effect, only one star-loop is ever active. It would be
43 ** possible to modify the code to maintain this context explicitly,
44 ** eliminating all recursive calls at the cost of some complication and
45 ** loss of clarity (and the ABORT stuff seems to be unclear enough by
46 ** itself). I think it would be unwise to try to get this into a
47 ** released version unless you have a good test data base to try it out
48 ** on.
49 */
50 /* YOU MUST NOT DEFINE ABORT TO 1, LEAVE AT -1 (would collide with TRUE)
51 */
52 #define ABORT -1
53 /* What character marks an inverted character class? */
54 #define NEGATE_CLASS '^'
55 /* Is "*" a common pattern? */
56 #define OPTIMIZE_JUST_STAR
57 /* Do tar(1) matching rules, which ignore a trailing slash? */
58 #undef MATCH_TAR_PATTERN
59 /*
60 * Match text and p, return TRUE (match), FALSE (no match), or ABORT
61 * (quick, no match). */
62 static int
63 DoMatch(const char *text, const char *p)
64 {
65 int last;
66 int matched;
67 int reverse;
68
69 for (; *p; text++, p++) {
70 if (*text == '\0' && *p != '*')
71 return ABORT;
72 switch (*p) {
73 case '\\':
74 /* Literal match with following character. */
75 p++;
76 /* FALLTHROUGH */
77 default:
78 if (*text != *p)
79 return FALSE;
80 continue;
81 case '?':
82 /* Match anything. */
83 continue;
84 case '*':
85 while (*++p == '*')
86 /* Consecutive stars act just like one. */
87 continue;
88 if (*p == '\0')
89 /* Trailing star matches everything. */
90 return TRUE;
91 while (*text)
92 if ((matched = DoMatch(text++, p)))
93 return matched;
94 return ABORT;
95 case '[':
96 reverse = p[1] == NEGATE_CLASS ? TRUE : FALSE;
97 if (reverse)
98 /* Inverted character class. */
99 p++;
100 matched = FALSE;
101 if (p[1] == ']' || p[1] == '-')
102 if (*++p == *text)
103 matched = TRUE;
104 for (last = *p; *++p && *p != ']'; last = *p)
105 /* This next line requires a good C compiler. */
106 if (*p == '-' && p[1] != ']'
107 ? *text <= *++p && *text >= last : *text == *p)
108 matched = TRUE;
109 if (matched == reverse)
110 return FALSE;
111 continue;
112 }
113 }
114 #ifdef MATCH_TAR_PATTERN
115 if (*text == '/')
116 return TRUE;
117 #endif /* MATCH_TAR_PATTERN */
118 return *text == '\0';
119 }
120
121 /*
122 ** User-level routine. Returns TRUE or FALSE.
123 ** This routine was borrowed from Rich Salz and appeared first in INN.
124 */
125 int
126 wildmat(const char *text, const char *p)
127 {
128 #ifdef OPTIMIZE_JUST_STAR
129 if (p[0] == '*' && p[1] == '\0')
130 return TRUE;
131 #endif /* OPTIMIZE_JUST_STAR */
132 return (DoMatch(text, p) == TRUE) ? TRUE : FALSE;
133 }
134
135 #ifdef TEST
136 #include <stdio.h>
137
138 int main(void)
139 {
140 char p[8000]; /* RATS: ignore */
141 char text[8000]; /* RATS: ignore */
142
143 printf("Wildmat tester. Enter pattern, then strings to test.\n");
144 printf("A blank line gets prompts for a new pattern; a blank pattern\n");
145 printf("exits the program.\n");
146
147 for ( ; ; ) {
148 printf("\nEnter pattern: ");
149 (void)fflush(stdout);
150 if (fgets(p, sizeof(p), stdin) == NULL || p[0] == '\n' || !*p)
151 break;
152 for ( ; ; ) {
153 printf("Enter text: ");
154 (void)fflush(stdout);
155 if (fgets(text, sizeof(text), stdin) == NULL)
156 exit(0);
157 if (text[0] == '\n' || !*p)
158 /* Blank line; go back and get a new pattern. */
159 break;
160 printf(" %s\n", wildmat(text, p) ? "YES" : "NO");
161 }
162 }
163
164 exit(0);
165 /* NOTREACHED */
166 }
167 #endif /* TEST */