]> mj.ucw.cz Git - libucw.git/blob - lib/kmp-search.h
Removed KMP_ADD_EXTRA_VAR and some useless parenteses.
[libucw.git] / lib / kmp-search.h
1 /*
2  *      Knuth-Morris-Pratt's Substring Search for N given strings
3  *
4  *      (c) 1999--2005, Robert Spalek <robert@ucw.cz>
5  *      (c) 2006, Pavel Charvat <pchar@ucw.cz>
6  *
7  *      (In fact, the algorithm is usually referred to as Aho-McCorasick,
8  *      but that's just an extension of KMP to multiple strings.)
9  */
10
11 /*
12  *  This is not a normal header file, it's a generator of KMP algorithm.
13  *  Each time you include it with parameters set in the corresponding
14  *  preprocessor macros, it generates KMP structures and functions
15  *  with the parameters given. Macros marked with [*] are mandatory.
16  *
17  *  [*] KMPS_PREFIX(x)          macro to add a name prefix (used on all global names
18  *                              defined by the KMP search generator)
19  *  [*] KMPS_KMP_PREFIX(x)      prefix used for lib/kmp.h;
20  *                              more variants of kmp-search can be used for single lib/kmp.h
21  *
22  *  KMPS_SOURCE                 user-defined search input (together with KMPS_GET_CHAR);
23  *                              if unset, the one from lib/kmp.h is used
24  *  KMPS_GET_CHAR(kmp,src,s)
25  *
26  *  KMPS_ADD_CONTROLS           add control characters at both ends of the input string
27  *  KMPS_MERGE_CONTROLS         merge adjacent control characters to a single one
28  *
29  *  KMPS_VARS
30  *
31  *  KMPS_INIT(kmp,src,s)
32  *  KMPS_EXIT(kmp,src,s)
33  *  KMPS_STEP(kmp,src,s)
34  *  KMPS_FOUND(kmp,src,s)
35  *  KMPS_FOUND_CHAIN(kmp,src,s)
36  *
37  *  KMPS_WANT_BEST
38  */
39
40 #define P(x) KMPS_PREFIX(x)
41 #define KP(x) KMPS_KMP_PREFIX(x)
42
43 #ifdef KMPS_SOURCE
44 typedef KMPS_SOURCE P(search_source_t);
45 #else
46 typedef KP(source_t) P(search_source_t);
47 #endif
48
49 #ifndef KMPS_GET_CHAR
50 #define KMPS_GET_CHAR(kmp,src,s) (KP(get_char)(kmp, &src, &s->c))
51 #endif
52
53 struct P(search) {
54   struct KP(state) *s;          /* current state */
55   struct KP(state) *out;        /* output state */
56 # ifdef KMPS_WANT_BEST
57   struct KP(state) *best;       /* longest match */
58 # endif
59   KP(char_t) c;                 /* last character */
60 # ifdef KMPS_ADD_CONTROLS
61   uns eof;
62 # endif
63 # ifdef KMPS_VARS
64   struct {
65     KMPS_VARS
66   } u;                          /* user-defined */
67 # endif
68 };
69
70 static void
71 P(search) (struct KP(struct) *kmp, struct P(search) *s, P(search_source_t) src)
72 {
73   s->s = &kmp->null;
74 # ifdef KMPS_WANT_BEST
75   s->best = &kmp->null;
76 # endif
77 # ifdef KMPS_ADD_CONTROLS 
78   s->c = KP(control)();
79   s->eof = 0;
80 # else
81   s->c = 0;
82 # endif  
83 # ifdef KMPS_INIT
84   { KMPS_INIT(kmp, src, s); }
85 # endif
86 # ifndef KMPS_ADD_CONTROLS  
87   goto start_read;
88 #endif  
89   for (;;)
90   {
91     for (struct KP(state) *t = s->s; t && !(s->s = KP(hash_find)(&kmp->hash, t, s->c)); t = t->back);
92     s->s = s->s ? : &kmp->null;
93
94 #   ifdef KMPS_STEP
95     { KMPS_STEP(kmp, src, s); }
96 #   endif
97
98 #   if defined(KMPS_FOUND) || defined(KMPS_FOUND_CHAIN) || defined(KMPS_WANT_BEST)
99     s->out = s->s->len ? s->s : s->s->next;
100     if (s->out)
101       {
102 #       ifdef KMPS_WANT_BEST
103         if (s->out->len > s->best->len)
104           s->best = s->out;
105 #       endif   
106         #ifdef KMPS_FOUND_CHAIN
107         { KMPS_FOUND_CHAIN(kmp, src, s); }
108 #       endif
109 #       ifdef KMPS_FOUND
110         do
111           { KMPS_FOUND(kmp, src, s); }
112         while (s->out = s->out->next);
113 #       endif   
114       }
115 #   endif
116
117 #   ifdef KMPS_ADD_CONTROLS    
118     if (s->eof)
119       break;
120 #   endif    
121
122 #   ifndef KMPS_ADD_CONTROLS    
123 start_read: ;
124 #   endif    
125 #   ifdef KMPS_MERGE_CONTROLS
126     KP(char_t) last_c = s->c;
127 #   endif
128
129     do
130       {
131         if (!KMPS_GET_CHAR(kmp, src, s))
132           {
133 #           ifdef KMPS_ADD_CONTROLS
134             if (!KP(is_control)(kmp, s->c))
135               {
136                 s->c = KP(control)();
137                 s->eof = 1;
138                 break;
139               }
140 #           endif
141             goto exit;
142           }
143       }
144     while (0
145 #     ifdef KMPS_MERGE_CONTROLS
146       || (KP(is_control)(kmp, last_c) && KP(is_control)(kmp, s->c))
147 #     endif
148       );
149   }
150 exit: ;
151 # ifdef KMPS_EXIT
152   { KMPS_EXIT(kmp, src, s); }
153 # endif
154 }
155
156 static inline void
157 P(run) (struct KP(struct) *kmp, P(search_source_t) src)
158 {
159   struct P(search) search;
160   P(search)(kmp, &search, src);
161 }
162
163 #undef P
164 #undef KMPS_PREFIX
165 #undef KMPS_KMP_PREFIX
166 #undef KMPS_SOURCE
167 #undef KMPS_GET_CHAR
168 #undef KMPS_ADD_CONTROLS
169 #undef KMPS_MERGE_CONTROLS
170 #undef KMPS_VARS
171 #undef KMPS_INIT
172 #undef KMPS_EXIT
173 #undef KMPS_FOUND
174 #undef KMPS_FOUND_CHAIN
175 #undef KMPS_STEP
176 #undef KMPS_WANT_BEST