leafnode  1.12.0
About: Leafnode is a store & forward NNTP proxy for small (dialup) sites.
  Fossies Dox: leafnode-1.12.0.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

wildmat.c
Go to the documentation of this file.
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). */
62static int
63DoMatch(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*/
125int
126wildmat(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
138int 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 */
int main(void)
Definition: amiroot.c:12
#define TRUE
Definition: leafnode.h:29
#define FALSE
Definition: leafnode.h:32
#define NEGATE_CLASS
Definition: wildmat.c:54
int wildmat(const char *text, const char *p)
Definition: wildmat.c:126
#define ABORT
Definition: wildmat.c:52
static int DoMatch(const char *text, const char *p)
Definition: wildmat.c:63