11825bd4 |
1 | #include "tweak.h" |
2 | |
6e182d98 |
3 | #include <stdio.h> |
4 | #include <stdlib.h> |
5 | #include <string.h> |
6 | |
a63728c7 |
7 | static DFA build_dfa (char *pattern, int len) |
8 | { |
6e182d98 |
9 | int i, j, k, b; |
a63728c7 |
10 | char *tmp = malloc(len); |
11 | DFA dfa = malloc(len * sizeof(*dfa)); |
6e182d98 |
12 | |
a63728c7 |
13 | if (!dfa) |
14 | return NULL; |
15 | if (!tmp) |
16 | return NULL; |
6e182d98 |
17 | |
18 | memcpy (tmp, pattern, len); |
19 | |
20 | for (i=len; i-- ;) { |
21 | j = i+1; |
22 | for (b=0; b<256; b++) { |
23 | dfa[i][b] = 0; |
24 | if (memchr(pattern, b, len)) { |
25 | tmp[j-1] = b; |
26 | for (k=1; k<=j; k++) |
27 | if (!memcmp(tmp+j-k, pattern, k)) |
28 | dfa[i][b] = k; |
29 | } |
30 | } |
31 | } |
a63728c7 |
32 | |
6e182d98 |
33 | return dfa; |
34 | } |
35 | |
a63728c7 |
36 | Search *build_search(char *pattern, int len) |
37 | { |
38 | Search *ret = malloc(sizeof(Search)); |
39 | char *revpat = malloc(len); |
40 | int i; |
41 | |
42 | ret->len = len; |
43 | ret->forward = build_dfa(pattern, len); |
44 | for (i = 0; i < len; i++) |
45 | revpat[i] = pattern[len-1-i]; |
46 | ret->reverse = build_dfa(revpat, len); |
47 | |
48 | return ret; |
6e182d98 |
49 | } |
50 | |
a63728c7 |
51 | void free_search(Search *s) |
52 | { |
53 | free(s->forward); |
54 | free(s->reverse); |
55 | free(s); |
6e182d98 |
56 | } |