Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
match.inl
Go to the documentation of this file.
1/* Reimplementation of pattern matching */
2/* This file is part of the CivetWeb web server.
3 * See https://github.com/civetweb/civetweb/
4 */
5
6
7/* Initialize structure with 0 matches */
8static void
10{
11 mcx->num_matches = 0;
12 memset(mcx->match, 0, sizeof(mcx->match));
13}
14
15
16/* Add a new match to the list of matches */
17static void
18match_context_push(const char *str, size_t len, struct mg_match_context *mcx)
19{
20 if (mcx->num_matches < MG_MATCH_CONTEXT_MAX_MATCHES) {
21 mcx->match[mcx->num_matches].str = str;
22 mcx->match[mcx->num_matches].len = len;
23 mcx->num_matches++;
24 }
25}
26
27
28static ptrdiff_t
29mg_match_impl(const char *pat,
30 size_t pat_len,
31 const char *str,
32 struct mg_match_context *mcx)
33{
34 /* Parse string */
35 size_t i_pat = 0; /* Pattern index */
36 size_t i_str = 0; /* Pattern index */
37
38 int case_sensitive = ((mcx != NULL) ? mcx->case_sensitive : 0); /* 0 or 1 */
39
40 while (i_pat < pat_len) {
41
42 /* Pattern ? matches one character, except / and NULL character */
43 if ((pat[i_pat] == '?') && (str[i_str] != '\0')
44 && (str[i_str] != '/')) {
45 size_t i_str_start = i_str;
46 do {
47 /* Advance as long as there are ? */
48 i_pat++;
49 i_str++;
50 } while ((i_pat < pat_len) && (pat[i_pat] == '?')
51 && (str[i_str] != '\0') && (str[i_str] != '/'));
52
53 /* If we have a match context, add the substring we just found */
54 if (mcx) {
56 }
57
58 /* Reached end of pattern ? */
59 if (i_pat == pat_len) {
60 return (ptrdiff_t)i_str;
61 }
62 }
63
64 /* Pattern $ matches end of string */
65 if (pat[i_pat] == '$') {
66 return (str[i_str] == '\0') ? (ptrdiff_t)i_str : -1;
67 }
68
69 /* Pattern * or ** matches multiple characters */
70 if (pat[i_pat] == '*') {
71 size_t len; /* length matched by "*" or "**" */
72 ptrdiff_t ret;
73
74 i_pat++;
75 if ((i_pat < pat_len) && (pat[i_pat] == '*')) {
76 /* Pattern ** matches all */
77 i_pat++;
78 len = strlen(str + i_str);
79 } else {
80 /* Pattern * matches all except / character */
81 len = strcspn(str + i_str, "/");
82 }
83
84 if (i_pat == pat_len) {
85 /* End of pattern reached. Add all to match context. */
86 if (mcx) {
88 }
89 return ((ptrdiff_t)(i_str + len));
90 }
91
92 /* This loop searches for the longest possible match */
93 do {
95 (pat_len - (size_t)i_pat),
96 str + i_str + len,
97 mcx);
98 } while ((ret == -1) && (len-- > 0));
99
100 /* If we have a match context, add the substring we just found */
101 if (ret >= 0) {
102 if (mcx) {
104 }
105 return ((ptrdiff_t)i_str + ret + (ptrdiff_t)len);
106 }
107
108 return -1;
109 }
110
111
112 /* Single character compare */
113 if (case_sensitive) {
114 if (pat[i_pat] != str[i_str]) {
115 /* case sensitive compare: mismatch */
116 return -1;
117 }
118 } else if (lowercase(&pat[i_pat]) != lowercase(&str[i_str])) {
119 /* case insensitive compare: mismatch */
120 return -1;
121 }
122
123 i_pat++;
124 i_str++;
125 }
126 return (ptrdiff_t)i_str;
127}
128
129
130static ptrdiff_t
132 size_t pat_len,
133 const char *str,
134 struct mg_match_context *mcx)
135{
136 const char *match_alternative = (const char *)memchr(pat, '|', pat_len);
137
138 if (mcx != NULL) {
140 }
141
142 while (match_alternative != NULL) {
143 /* Split at | for alternative match */
144 size_t left_size = (size_t)(match_alternative - pat);
145
146 /* Try left string first */
147 ptrdiff_t ret = mg_match_impl(pat, left_size, str, mcx);
148 if (ret >= 0) {
149 /* A 0-byte match is also valid */
150 return ret;
151 }
152
153 /* Reset possible incomplete match data */
154 if (mcx != NULL) {
156 }
157
158 /* If no match: try right side */
159 pat += left_size + 1;
160 pat_len -= left_size + 1;
161 match_alternative = (const char *)memchr(pat, '|', pat_len);
162 }
163
164 /* Handled all | operators. This is the final string. */
165 return mg_match_impl(pat, pat_len, str, mcx);
166}
167
168
169static int
170match_compare(const void *p1, const void *p2, void *user)
171{
172 const struct mg_match_element *e1 = (const struct mg_match_element *)p1;
173 const struct mg_match_element *e2 = (const struct mg_match_element *)p2;
174
175 /* unused */
176 (void)user;
177
178 if (e1->str > e2->str) {
179 return +1;
180 }
181 if (e1->str < e2->str) {
182 return -1;
183 }
184 return 0;
185}
186
187
188#if defined(MG_EXPERIMENTAL_INTERFACES)
190#else
191static
192#endif
193ptrdiff_t
194mg_match(const char *pat, const char *str, struct mg_match_context *mcx)
195{
196 size_t pat_len = strlen(pat);
197 ptrdiff_t ret = mg_match_alternatives(pat, pat_len, str, mcx);
198 if (mcx != NULL) {
199 if (ret < 0) {
200 /* Remove possible incomplete data */
202 } else {
203 /* Join "?*" to one pattern. */
204 size_t i, j;
205
206 /* Use difference of two array elements instead of sizeof, since
207 * there may be some additional padding bytes. */
208 size_t elmsize =
209 (size_t)(&mcx->match[1]) - (size_t)(&mcx->match[0]);
210
211 /* First sort the matches by address ("str" begin to end) */
212 mg_sort(mcx->match, mcx->num_matches, elmsize, match_compare, NULL);
213
214 /* Join consecutive matches */
215 i = 1;
216 while (i < mcx->num_matches) {
217 if ((mcx->match[i - 1].str + mcx->match[i - 1].len)
218 == mcx->match[i].str) {
219 /* Two matches are consecutive. Join length. */
220 mcx->match[i - 1].len += mcx->match[i].len;
221
222 /* Shift all list elements. */
223 for (j = i + 1; j < mcx->num_matches; j++) {
224 mcx->match[j - 1].len = mcx->match[j].len;
225 mcx->match[j - 1].str = mcx->match[j].str;
226 }
227
228 /* Remove/blank last list element. */
229 mcx->num_matches--;
230 mcx->match[mcx->num_matches].str = NULL;
231 mcx->match[mcx->num_matches].len = 0;
232
233 } else {
234 i++;
235 }
236 }
237 }
238 }
239 return ret;
240}
241
242
243static ptrdiff_t
244match_prefix(const char *pattern, size_t pattern_len, const char *str)
245{
246 if (pattern == NULL) {
247 return -1;
248 }
249 return mg_match_alternatives(pattern, pattern_len, str, NULL);
250}
251
252
253static ptrdiff_t
254match_prefix_strlen(const char *pattern, const char *str)
255{
256 if (pattern == NULL) {
257 return -1;
258 }
259 return mg_match_alternatives(pattern, strlen(pattern), str, NULL);
260}
261
262/* End of match.inl */
ROOT::Detail::TRangeCast< T, true > TRangeDynCast
TRangeDynCast is an adapter class that allows the typed iteration through a TCollection.
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t Int_t Int_t UInt_t UInt_t Rectangle_t Int_t Int_t Window_t TString Int_t GCValues_t GetPrimarySelectionOwner GetDisplay GetScreen GetColormap GetNativeEvent const char const char dpyName wid window const char font_name cursor keysym reg const char only_if_exist regb h Point_t winding char text const char depth char const char Int_t count const char ColorStruct_t color const char Pixmap_t Pixmap_t PictureAttributes_t attr const char char ret_data h unsigned char height h Atom_t Int_t ULong_t ULong_t unsigned char prop_list Atom_t Atom_t Atom_t Time_t UChar_t len
static int lowercase(const char *s)
Definition civetweb.c:3084
#define MG_MATCH_CONTEXT_MAX_MATCHES
Definition civetweb.h:1370
#define CIVETWEB_API
Definition civetweb.h:43
static ptrdiff_t mg_match_impl(const char *pat, size_t pat_len, const char *str, struct mg_match_context *mcx)
Definition match.inl:29
static void match_context_push(const char *str, size_t len, struct mg_match_context *mcx)
Definition match.inl:18
static ptrdiff_t match_prefix_strlen(const char *pattern, const char *str)
Definition match.inl:254
static void match_context_reset(struct mg_match_context *mcx)
Definition match.inl:9
static ptrdiff_t mg_match(const char *pat, const char *str, struct mg_match_context *mcx)
Definition match.inl:194
static ptrdiff_t mg_match_alternatives(const char *pat, size_t pat_len, const char *str, struct mg_match_context *mcx)
Definition match.inl:131
static ptrdiff_t match_prefix(const char *pattern, size_t pattern_len, const char *str)
Definition match.inl:244
static int match_compare(const void *p1, const void *p2, void *user)
Definition match.inl:170
static void mg_sort(void *data, size_t elemcount, size_t elemsize, int(*compfunc)(const void *data1, const void *data2, void *userarg), void *userarg)
Definition sort.inl:5