]> mj.ucw.cz Git - libucw.git/blob - lib/kmp.h
shut up, gcc
[libucw.git] / lib / kmp.h
1 /*
2  *      Knuth-Morris-Pratt's Substring Search for N given strings
3  * 
4  *      (c) 1999--2005, Robert Spalek <robert@ucw.cz>
5  *
6  *      This is a preprocessor template: you need to set KMP_GET_CHAR
7  *      to a macro for reading a single character from the input and
8  *      translating it according to the MF_xxx flags. See below for
9  *      some pre-defined values.
10  *
11  *      Don't touch this file, it can bite.
12  *
13  *      (In fact, the algorithm is usually referred to as Aho-McCorasick,
14  *      but that's just an extension of KMP to multiple strings.)
15  */
16
17 #ifndef _UCW_KMP_H
18 #define _UCW_KMP_H
19
20 #include "lib/lists.h"
21
22 /*
23  * Input conversion flags (the conversion is handled exclusively by the KMP_GET_CHAR
24  * macro, so you can define your own conversion modes, soo).
25  */
26 #define MF_TOLOWER      1
27 #define MF_UNACCENT     2
28 #define MF_ONLYALPHA    4       /* Convert non-alphas to KMP_CONTROL_CHAR */
29
30 #define KMP_CONTROL_CHAR ':'
31
32 /* Pre-defined input functions */
33
34 #define KMP_GET_RAW(pos, c, flags) c=*pos++
35
36 #define KMP_GET_ASCII(pos, c, flags) do { \
37         c = *pos++; \
38         if (c) { \
39                 if (flags & MF_TOLOWER) \
40                         c = Clocase(c); \
41                 if (flags & MF_ONLYALPHA && !Calpha(c)) \
42                         c = KMP_CONTROL_CHAR; \
43         } \
44 } while (0)
45
46 /* Types and structures */
47
48 typedef uns kmp_state_t;
49 typedef word kmp_char_t;
50
51 struct kmp_transition {
52         struct node n;                  /* link list of sons for a given node */
53         struct kmp_transition *next;    /* collision in the hash-table of all transitions */
54         kmp_state_t from, to;
55         kmp_char_t c;
56 };
57 struct kmp_transitions {
58         int count, size;
59         struct list *sons;              /* link-list of all sons for each given node */
60         uns hash_size;
61         struct kmp_transition **chain;  /* hash-table of [node, char]->son */
62 };
63
64 struct kmp_output {
65         struct kmp_output *next;        /* output link list for every node */
66         uns id;
67         uns len;
68 };
69
70 struct mempool;
71 struct kmp {
72         struct mempool *mp;
73         int modify_flags;               /* which nocase/noaccent mode is this kmp for */
74         int words_len;                  /* total length of searched words */
75         struct kmp_transitions g;       /* hash table of forward transitions of automat */
76         kmp_state_t *f;                 /* back transitions of automat */
77         struct kmp_output **out;        /* found words for every state */
78 };
79
80 struct kmp_result {
81         struct node n;                  /* strings with non-zero frequency are put into a link-list */
82         uns occur;
83 };
84
85 /* kmp.c */
86 struct kmp *kmp_new(struct mempool *mp, int words_len, uns modify_flags);
87 void kmp_enter_raw_string(struct kmp *kmp, const byte *str, uns id);
88 void kmp_build(struct kmp *kmp);
89
90 static inline void
91 kmp_get_char(const byte **str, kmp_char_t *c, uns modify_flags UNUSED)
92 {
93         while (1)
94         {
95                 kmp_char_t new_c;
96                 KMP_GET_CHAR((*str), new_c, modify_flags);
97                 if (new_c != KMP_CONTROL_CHAR || *c != KMP_CONTROL_CHAR)
98                 {
99                         *c = new_c;
100                         return;
101                 }
102         }
103 }
104
105 static inline void
106 kmp_enter_string(struct kmp *kmp, const byte *str, uns id)
107 {
108         /* To avoid dependencies between libucw and other libraries (which might
109          * be referenced by the KMP_GET_CHAR macro), we have to split kmp_enter_string()
110          * to a conversion wrapper (this function) and the rest, which resides in kmp.c
111          * and uses KMP_GET_RAW to read its input.
112          */
113         byte buf[3*strlen(str)+1], *str2 = buf;
114         kmp_char_t c = 0;
115         do
116         {
117                 kmp_get_char(&str, &c, kmp->modify_flags);
118                 str2 = utf8_put(str2, c);
119         }
120         while (c);
121         kmp_enter_raw_string(kmp, buf, id);
122 }
123
124 static inline uns
125 transition_hashf(struct kmp_transitions *l UNUSED, struct kmp_transition *tr)
126 {
127         return tr->from + (tr->c << 16);
128 }
129
130 static inline int
131 transition_compare(struct kmp_transition *a, struct kmp_transition *b)
132 {
133         if (a->from == b->from && a->c == b->c)
134                 return 0;
135         else
136                 return 1;
137 }
138
139 static inline struct kmp_transition **
140 transition_search(struct kmp_transitions *l, struct kmp_transition *tr)
141 {
142         uns hf = transition_hashf(l, tr) % l->hash_size;
143         struct kmp_transition **last = l->chain + hf;
144         while (*last && transition_compare(*last, tr))
145                 last = &(*last)->next;
146         ASSERT(last);
147         return last;
148 }
149
150 static inline void
151 add_result(struct list *nonzeroes, struct kmp_result *freq, struct kmp_output *out)
152 {
153         for (; out; out = out->next)
154                 if (!freq[out->id].occur++)
155                         add_tail(nonzeroes, &freq[out->id].n);
156 }
157
158 static inline byte *
159 kmp_search_internal(struct kmp *kmp, byte *str, uns len, struct list *nonzeroes, struct kmp_result *freq, struct kmp_output *out)
160   /* For every found string with id ID, it increments freq[ID].
161    * Also, it finds the longest among the leftmost matches.  */
162 {
163         byte *str_end = str + len;
164         kmp_state_t s = 0;
165         kmp_char_t c = KMP_CONTROL_CHAR;
166         struct kmp_transition tr, **prev;
167         byte eof = 0;
168         if (kmp->words_len <= 1)
169                 return NULL;
170         //TRACE(20, "kmp.c: Searching string %s", str);
171         byte *largest_match = NULL;
172         while (1)
173         {
174                 tr.from = s;
175                 tr.c = c;
176                 prev = transition_search(&kmp->g, &tr);
177                 while (tr.from && !*prev)
178                 {
179                         tr.from = kmp->f[ tr.from ];
180                         prev = transition_search(&kmp->g, &tr);
181                 }
182                 s = *prev ? (*prev)->to : 0;
183                 if (nonzeroes)
184                         add_result(nonzeroes, freq, kmp->out[s]);
185                 /* Beware that out->len is measured in modified characters of
186                  * the search pattern, hence it is not very reliable if you use
187                  * unaccenting.  */
188                 struct kmp_output *kout = kmp->out[s];
189                 if (kout && (!largest_match || str - kout->len <= largest_match))
190                 {
191                         largest_match = str - kout->len;
192                         if (out)
193                                 *out = *kout;
194                 }
195                 if (eof)
196                         break;
197                 if (str >= str_end)
198                         c = 0;
199                 else
200                         kmp_get_char((const byte **)&str, &c, kmp->modify_flags);
201                 if (!c)
202                 {
203                         /* Insert KMP_CONTROL_CHAR at the beginning and at the end too.  */
204                         c = KMP_CONTROL_CHAR;
205                         eof = 1;
206                 }
207         }
208         return largest_match;
209 }
210
211 static inline void
212 kmp_search(struct kmp *kmp, const byte *str, struct list *nonzeroes, struct kmp_result *freq)
213 {
214         kmp_search_internal(kmp, (byte*) str, strlen(str), nonzeroes, freq, NULL);
215 }
216
217 static inline byte *
218 kmp_find_first(struct kmp *kmp, byte *str, uns len, struct kmp_output *out)
219 {
220         return kmp_search_internal(kmp, str, len, NULL, NULL, out);
221 }
222
223 #endif