"Fossies" - the Fresh Open Source Software Archive 
Member "n2n-3.1.1/src/n2n_regex.c" (31 Mar 2022, 15897 Bytes) of package /linux/misc/n2n-3.1.1.tar.gz:
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 "n2n_regex.c" see the
Fossies "Dox" file reference documentation and the latest
Fossies "Diffs" side-by-side code changes report:
3.0_vs_3.1.1.
1 /**
2 * (C) 2007-22 - ntop.org and contributors
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 3 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not see see <http://www.gnu.org/licenses/>
16 *
17 */
18
19 // taken from https://github.com/kokke/tiny-regex-c
20 // under Unlicense as of August 4, 2020
21
22 /*
23 *
24 * Mini regex-module inspired by Rob Pike's regex code described in:
25 *
26 * http://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html
27 *
28 *
29 *
30 * Supports:
31 * ---------
32 * '.' Dot, matches any character
33 * '^' Start anchor, matches beginning of string -- NOTE: currently disabled (checking for full matches anyway)
34 * '$' End anchor, matches end of string -- NOTE: currently disabled (checking for full matches anyway)
35 * '*' Asterisk, match zero or more (greedy)
36 * '+' Plus, match one or more (greedy)
37 * '?' Question, match zero or one (non-greedy)
38 * '[abc]' Character class, match if one of {'a', 'b', 'c'}
39 * '[^abc]' Inverted class, match if NOT one of {'a', 'b', 'c'} -- NOTE: feature is currently broken!
40 * '[a-zA-Z]' Character ranges, the character set of the ranges { a-z | A-Z }
41 * '\s' Whitespace, \t \f \r \n \v and spaces
42 * '\S' Non-whitespace
43 * '\w' Alphanumeric, [a-zA-Z0-9_]
44 * '\W' Non-alphanumeric
45 * '\d' Digits, [0-9]
46 * '\D' Non-digits
47 *
48 *
49 */
50
51
52 #include "n2n.h"
53 #include "n2n_regex.h"
54
55 /* Definitions: */
56
57 #define MAX_REGEXP_OBJECTS 30 /* Max number of regex symbols in expression. */
58 #define MAX_CHAR_CLASS_LEN 40 /* Max length of character-class buffer in. */
59
60
61 enum { UNUSED, DOT, BEGIN, END, QUESTIONMARK, STAR, PLUS, CHAR_TYPE, CHAR_CLASS, INV_CHAR_CLASS, DIGIT, NOT_DIGIT, ALPHA, NOT_ALPHA, WHITESPACE, NOT_WHITESPACE, /* BRANCH */ };
62
63 typedef struct regex_t {
64 unsigned char type; /* CHAR_TYPE, STAR, etc. */
65 union {
66 unsigned char ch; /* the character itself */
67 unsigned char* ccl; /* OR a pointer to characters in class */
68 };
69 } regex_t;
70
71
72
73 /* Private function declarations: */
74 static int matchpattern (regex_t* pattern, const char* text, int* matchlength);
75 static int matchcharclass (char c, const char* str);
76 static int matchstar (regex_t p, regex_t* pattern, const char* text, int* matchlength);
77 static int matchplus (regex_t p, regex_t* pattern, const char* text, int* matchlength);
78 static int matchone (regex_t p, char c);
79 static int matchdigit (char c);
80 static int matchalpha (char c);
81 static int matchwhitespace (char c);
82 static int matchmetachar (char c, const char* str);
83 static int matchrange (char c, const char* str);
84 static int matchdot (char c);
85 static int ismetachar (char c);
86
87
88
89 /* Public functions: */
90 int re_match (const char* pattern, const char* text, int* matchlength) {
91
92 re_t re_p; /* pointer to (to be created) copy of compiled regex */
93 int ret = -1;
94
95 re_p = re_compile (pattern);
96 ret = re_matchp(re_p, text, matchlength);
97 free(re_p);
98
99 return(ret);
100 }
101
102 int re_matchp (re_t pattern, const char* text, int* matchlength) {
103
104 *matchlength = 0;
105
106 if(pattern != 0) {
107 if(pattern[0].type == BEGIN) {
108 return ((matchpattern(&pattern[1], text, matchlength)) ? 0 : -1);
109 } else {
110 int idx = -1;
111
112 do {
113 idx += 1;
114
115 if(matchpattern(pattern, text, matchlength)) {
116 if(text[0] == '\0') {
117 return -1;
118 }
119 return idx;
120 }
121 } while(*text++ != '\0');
122 }
123 }
124
125 return -1;
126 }
127
128 re_t re_compile (const char* pattern) {
129
130 /* The sizes of the two static arrays below substantiates the static RAM usage of this module.
131 MAX_REGEXP_OBJECTS is the max number of symbols in the expression.
132 MAX_CHAR_CLASS_LEN determines the size of buffer for chars in all char-classes in the expression. */
133 static regex_t re_compiled[MAX_REGEXP_OBJECTS];
134 re_t re_p; /* pointer to (to be created) copy of compiled regex in re_compiled */
135
136 static unsigned char ccl_buf[MAX_CHAR_CLASS_LEN];
137 int ccl_bufidx = 1;
138
139 char c; /* current char in pattern */
140 int i = 0; /* index into pattern */
141 int j = 0; /* index into re_compiled */
142
143 while(pattern[i] != '\0' && (j + 1 < MAX_REGEXP_OBJECTS)) {
144 c = pattern[i];
145
146 switch(c) {
147 /* Meta-characters: */
148 // case '^': { re_compiled[j].type = BEGIN; } break; <-- disabled (always full matches)
149 // case '$': { re_compiled[j].type = END; } break; <-- disabled (always full matches)
150 case '.': { re_compiled[j].type = DOT; } break;
151 case '*': { re_compiled[j].type = STAR; } break;
152 case '+': { re_compiled[j].type = PLUS; } break;
153 case '?': { re_compiled[j].type = QUESTIONMARK; } break;
154 /* case '|': { re_compiled[j].type = BRANCH; } break; <-- not working properly */
155
156 /* Escaped character-classes (\s \w ...): */
157 case '\\': {
158 if(pattern[i + 1] != '\0') {
159 /* Skip the escape-char '\\' */
160 i += 1;
161 /* ... and check the next */
162 switch(pattern[i]) {
163 /* Meta-character: */
164 case 'd': { re_compiled[j].type = DIGIT; } break;
165 case 'D': { re_compiled[j].type = NOT_DIGIT; } break;
166 case 'w': { re_compiled[j].type = ALPHA; } break;
167 case 'W': { re_compiled[j].type = NOT_ALPHA; } break;
168 case 's': { re_compiled[j].type = WHITESPACE; } break;
169 case 'S': { re_compiled[j].type = NOT_WHITESPACE; } break;
170
171 /* Escaped character, e.g. '.' */
172 default: {
173 re_compiled[j].type = CHAR_TYPE;
174 re_compiled[j].ch = pattern[i];
175 } break;
176 }
177 }
178 /* '\\' as last char in pattern -> invalid regular expression. */
179 /*
180 else
181 {
182 re_compiled[j].type = CHAR_TYPE;
183 re_compiled[j].ch = pattern[i];
184 }
185 */
186 } break;
187
188 /* Character class: */
189 case '[': {
190 /* Remember where the char-buffer starts. */
191 int buf_begin = ccl_bufidx;
192
193 /* Look-ahead to determine if negated */
194 if(pattern[i+1] == '^') {
195 re_compiled[j].type = INV_CHAR_CLASS;
196 i += 1; /* Increment i to avoid including '^' in the char-buffer */
197 } else {
198 re_compiled[j].type = CHAR_CLASS;
199 }
200
201 /* Copy characters inside [..] to buffer */
202 while((pattern[++i] != ']')
203 && (pattern[i] != '\0')) /* Missing ] */
204 {
205 if(pattern[i] == '\\') {
206 if(ccl_bufidx >= MAX_CHAR_CLASS_LEN - 1) {
207 //fputs("exceeded internal buffer!\n", stderr);
208 return 0;
209 }
210 ccl_buf[ccl_bufidx++] = pattern[i++];
211 } else if(ccl_bufidx >= MAX_CHAR_CLASS_LEN) {
212 //fputs("exceeded internal buffer!\n", stderr);
213 return 0;
214 }
215 ccl_buf[ccl_bufidx++] = pattern[i];
216 }
217 if(ccl_bufidx >= MAX_CHAR_CLASS_LEN) {
218 /* Catches cases such as [00000000000000000000000000000000000000][ */
219 //fputs("exceeded internal buffer!\n", stderr);
220 return 0;
221 }
222 /* Null-terminate string end */
223 ccl_buf[ccl_bufidx++] = 0;
224 re_compiled[j].ccl = &ccl_buf[buf_begin];
225 } break;
226
227 /* Other characters: */
228 default: {
229 re_compiled[j].type = CHAR_TYPE;
230 re_compiled[j].ch = c;
231 } break;
232 }
233 i += 1;
234 j += 1;
235 }
236 /* 'UNUSED' is a sentinel used to indicate end-of-pattern */
237 re_compiled[j].type = UNUSED;
238
239 re_p = (re_t)calloc(1, sizeof(re_compiled));
240 memcpy (re_p, re_compiled, sizeof(re_compiled));
241
242 return (re_t) re_p;
243 }
244
245 void re_print (regex_t* pattern) {
246
247 const char* types[] = { "UNUSED", "DOT", "BEGIN", "END", "QUESTIONMARK", "STAR", "PLUS", "CHAR_TYPE", "CHAR_CLASS", "INV_CHAR_CLASS", "DIGIT", "NOT_DIGIT", "ALPHA", "NOT_ALPHA", "WHITESPACE" , "NOT_WHITESPACE", /* "BRANCH" */ };
248 int i;
249 int j;
250 char c;
251
252 for(i = 0; i < MAX_REGEXP_OBJECTS; ++i) {
253 if(pattern[i].type == UNUSED) {
254 break;
255 }
256
257 printf("type: %s", types[pattern[i].type]);
258 if((pattern[i].type == CHAR_CLASS) || (pattern[i].type == INV_CHAR_CLASS)) {
259 printf(" [");
260 for(j = 0; j < MAX_CHAR_CLASS_LEN; ++j) {
261 c = pattern[i].ccl[j];
262 if((c == '\0') || (c == ']')) {
263 break;
264 }
265 printf("%c", c);
266 }
267 printf("]");
268 } else if(pattern[i].type == CHAR_TYPE) {
269 printf(" '%c'", pattern[i].ch);
270 }
271 printf("\n");
272 }
273 }
274
275
276
277 /* Private functions: */
278 static int matchdigit (char c) {
279
280 return ((c >= '0') && (c <= '9'));
281 }
282
283 static int matchalpha (char c) {
284
285 return ((c >= 'a') && (c <= 'z')) || ((c >= 'A') && (c <= 'Z'));
286 }
287
288 static int matchwhitespace (char c) {
289
290 return ((c == ' ') || (c == '\t') || (c == '\n') || (c == '\r') || (c == '\f') || (c == '\v'));
291 }
292
293 static int matchalphanum (char c) {
294
295 return ((c == '_') || matchalpha(c) || matchdigit(c));
296 }
297
298 static int matchrange (char c, const char* str) {
299
300 return ((c != '-') && (str[0] != '\0') && (str[0] != '-') &&
301 (str[1] == '-') && (str[1] != '\0') &&
302 (str[2] != '\0') && ((c >= str[0]) && (c <= str[2])));
303 }
304
305 static int matchdot (char c) {
306
307 return ((c != '\n') && (c != '\r'));
308 }
309
310 static int ismetachar (char c) {
311
312 return ((c == 's') || (c == 'S') || (c == 'w') || (c == 'W') || (c == 'd') || (c == 'D'));
313 }
314
315 static int matchmetachar (char c, const char* str) {
316
317 switch(str[0]) {
318 case 'd': return matchdigit(c);
319 case 'D': return !matchdigit(c);
320 case 'w': return matchalphanum(c);
321 case 'W': return !matchalphanum(c);
322 case 's': return matchwhitespace(c);
323 case 'S': return !matchwhitespace(c);
324 default: return (c == str[0]);
325 }
326 }
327
328 static int matchcharclass (char c, const char* str) {
329
330 do {
331 if(matchrange(c, str)) {
332 return 1;
333 } else if(str[0] == '\\') {
334 /* Escape-char: increment str-ptr and match on next char */
335 str += 1;
336 if(matchmetachar(c, str)) {
337 return 1;
338 } else if((c == str[0]) && !ismetachar(c)) {
339 return 1;
340 }
341 } else if(c == str[0]) {
342 if(c == '-') {
343 return ((str[-1] == '\0') || (str[1] == '\0'));
344 } else {
345 return 1;
346 }
347 }
348 } while(*str++ != '\0');
349
350 return 0;
351 }
352
353 static int matchone (regex_t p, char c) {
354
355 switch(p.type) {
356 case DOT: return matchdot(c);
357 case CHAR_CLASS: return matchcharclass(c, (const char*)p.ccl);
358 case INV_CHAR_CLASS: return !matchcharclass(c, (const char*)p.ccl);
359 case DIGIT: return matchdigit(c);
360 case NOT_DIGIT: return !matchdigit(c);
361 case ALPHA: return matchalphanum(c);
362 case NOT_ALPHA: return !matchalphanum(c);
363 case WHITESPACE: return matchwhitespace(c);
364 case NOT_WHITESPACE: return !matchwhitespace(c);
365 default: return (p.ch == c);
366 }
367 }
368
369 static int matchstar (regex_t p, regex_t* pattern, const char* text, int* matchlength) {
370
371 int prelen = *matchlength;
372 const char* prepoint = text;
373
374 while((text[0] != '\0') && matchone(p, *text)) {
375 text++;
376 (*matchlength)++;
377 }
378
379 while(text >= prepoint) {
380 if(matchpattern(pattern, text--, matchlength)) {
381 return 1;
382 }
383 (*matchlength)--;
384 }
385
386 *matchlength = prelen;
387
388 return 0;
389 }
390
391 static int matchplus (regex_t p, regex_t* pattern, const char* text, int* matchlength) {
392
393 const char* prepoint = text;
394
395 while((text[0] != '\0') && matchone(p, *text)) {
396 text++;
397 (*matchlength)++;
398 }
399
400 while(text > prepoint) {
401 if(matchpattern(pattern, text--, matchlength)) {
402 return 1;
403 }
404 (*matchlength)--;
405 }
406
407 return 0;
408 }
409
410 static int matchquestion (regex_t p, regex_t* pattern, const char* text, int* matchlength) {
411
412 if(p.type == UNUSED) {
413 return 1;
414 }
415
416 if(matchpattern(pattern, text, matchlength)) {
417 return 1;
418 }
419
420 if(*text && matchone(p, *text++)) {
421 if(matchpattern(pattern, text, matchlength)) {
422 (*matchlength)++;
423 return 1;
424 }
425 }
426
427 return 0;
428 }
429
430
431 #if 0
432
433 /* Recursive matching */
434 static int matchpattern (regex_t* pattern, const char* text, int *matchlength) {
435
436 int pre = *matchlength;
437
438 if((pattern[0].type == UNUSED) || (pattern[1].type == QUESTIONMARK)) {
439 return matchquestion(pattern[1], &pattern[2], text, matchlength);
440 } else if(pattern[1].type == STAR) {
441 return matchstar(pattern[0], &pattern[2], text, matchlength);
442 } else if(pattern[1].type == PLUS) {
443 return matchplus(pattern[0], &pattern[2], text, matchlength);
444 } else if((pattern[0].type == END) && pattern[1].type == UNUSED) {
445 return text[0] == '\0';
446 } else if((text[0] != '\0') && matchone(pattern[0], text[0])) {
447 (*matchlength)++;
448 return matchpattern(&pattern[1], text+1);
449 } else {
450 *matchlength = pre;
451 return 0;
452 }
453 }
454
455 #else
456
457 /* Iterative matching */
458 static int matchpattern (regex_t* pattern, const char* text, int* matchlength) {
459
460 int pre = *matchlength;
461
462 do {
463 if((pattern[0].type == UNUSED) || (pattern[1].type == QUESTIONMARK)) {
464 return matchquestion(pattern[0], &pattern[2], text, matchlength);
465 } else if(pattern[1].type == STAR) {
466 return matchstar(pattern[0], &pattern[2], text, matchlength);
467 } else if(pattern[1].type == PLUS) {
468 return matchplus(pattern[0], &pattern[2], text, matchlength);
469 } else if((pattern[0].type == END) && pattern[1].type == UNUSED) {
470 return (text[0] == '\0');
471 }
472 /* Branching is not working properly
473 else if (pattern[1].type == BRANCH)
474 {
475 return (matchpattern(pattern, text) || matchpattern(&pattern[2], text));
476 }
477 */
478 (*matchlength)++;
479 } while((text[0] != '\0') && matchone(*pattern++, *text++));
480
481 *matchlength = pre;
482
483 return 0;
484 }
485
486 #endif