]> mj.ucw.cz Git - libucw.git/blob - lib/kmp.h
419129be67817a7ae2a442e921a0d53ba9252a54
[libucw.git] / lib / kmp.h
1 /*
2  *      Knuth-Morris-Pratt's search automat for N given strings
3  * 
4  *      (c) 1999--2005, Robert Spalek <robert@ucw.cz>
5  *
6  *      Set KMP_TRANSLATE to one of {UNICODE,ASCII,NO}_TRANSLATE.
7  *
8  *      Don't touch this file, because it is a mess.
9  */
10
11 #ifndef _UCW_KMP_H
12 #define _UCW_KMP_H
13
14 #include "lib/lists.h"
15
16 #define MF_TOLOWER      1
17 #define MF_UNACCENT     2
18 #define MF_ONLYALPHA    4
19         /* how to modify characters in the string */
20 #define CONTROL_CHAR    ':'
21         /* all non-alphabetic characters are treated as CONTROL_CHAR */
22
23 #define UNICODE_TRANSLATE(new_c, c, flags)      do { \
24         if (!c) \
25                 new_c = 0; \
26         else { \
27                 if (flags & MF_TOLOWER) \
28                         c = Utolower(c); \
29                 if (flags & MF_UNACCENT) \
30                         c = Uunaccent(c); \
31                 if (flags & MF_ONLYALPHA && !Ualpha(c)) \
32                         c = CONTROL_CHAR; \
33                 new_c = c; \
34         } \
35 } while (0)
36 #define ASCII_TRANSLATE(new_c, c, flags)        do { \
37         if (!c) \
38                 new_c = 0; \
39         else { \
40                 if (flags & MF_TOLOWER) \
41                         c = Clocase(c); \
42                 if (flags & MF_ONLYALPHA && !Calpha(c)) \
43                         c = CONTROL_CHAR; \
44                 new_c = c; \
45         } \
46 } while (0)
47 #define NO_TRANSLATE(new_c, c, flags)   do { new_c = c; } while (0)
48
49 typedef uns kmp_state_t;
50 typedef word kmp_char_t;
51
52 struct kmp_transition {
53         struct node n;                  /* link list of sons for a given node */
54         struct kmp_transition *next;    /* collision in the hash-table of all transitions */
55         kmp_state_t from, to;
56         kmp_char_t c;
57 };
58 struct kmp_transitions {
59         int count, size;
60         struct list *sons;              /* link-list of all sons for each given node */
61         uns hash_size;
62         struct kmp_transition **chain;  /* hash-table of [node, char]->son */
63 };
64
65 struct kmp_output {
66         struct kmp_output *next;        /* output link list for every node */
67         uns id;
68         uns len;
69 };
70
71 struct mempool;
72 struct kmp {
73         struct mempool *mp;
74         int modify_flags;               /* which nocase/noaccent mode is this kmp for */
75         int words_len;                  /* total length of searched words */
76         struct kmp_transitions g;       /* hash table of forward transitions of automat */
77         kmp_state_t *f;                 /* back transitions of automat */
78         struct kmp_output **out;        /* found words for every state */
79 };
80
81 /* kmp.c */
82 struct kmp *kmp_new(struct mempool *mp, int words_len, uns modify_flags);
83 void kmp_enter_raw_string(struct kmp *kmp, const byte *str, uns id);
84 void kmp_build(struct kmp *kmp);
85
86 static inline void
87 kmp_get_char(const byte **str, kmp_char_t *c, uns modify_flags UNUSED)
88 {
89         while (1)
90         {
91                 uns w;
92                 kmp_char_t new_c;
93                 GET_TAGGED_CHAR((*str), w);
94                 if (w >= 0x80000000)
95                         w = CONTROL_CHAR;
96                 KMP_TRANSLATE(new_c, w, modify_flags);
97                 if (new_c != CONTROL_CHAR || *c != 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         /* Ugly hack to avoid linking libucw with libcharset:
109          * Convert the entered string here in the header and then call the
110          * library function.  This function calls kmp_get_char() without any
111          * conversion.  */
112         byte buf[strlen(str)+1], *str2 = buf;
113         kmp_char_t c;
114         do
115         {
116                 kmp_get_char(&str, &c, kmp->modify_flags);
117                 str2 = utf8_put(str2, c);
118         }
119         while (c);
120         kmp_enter_raw_string(kmp, buf, id);
121 }
122
123 struct kmp_result {
124         struct node n;                  /* strings with non-zero frequency are put into a link-list */
125         uns occur;
126 };
127
128 static inline uns
129 transition_hashf(struct kmp_transitions *l UNUSED, struct kmp_transition *tr)
130 {
131         return tr->from + (tr->c << 16);
132 }
133
134 static inline int
135 transition_compare(struct kmp_transition *a, struct kmp_transition *b)
136 {
137         if (a->from == b->from && a->c == b->c)
138                 return 0;
139         else
140                 return 1;
141 }
142
143 static inline struct kmp_transition **
144 transition_search(struct kmp_transitions *l, struct kmp_transition *tr)
145 {
146         uns hf = transition_hashf(l, tr) % l->hash_size;
147         struct kmp_transition **last = l->chain + hf;
148         while (*last && transition_compare(*last, tr))
149                 last = &(*last)->next;
150         ASSERT(last);
151         return last;
152 }
153
154 static inline void
155 add_result(struct list *nonzeroes, struct kmp_result *freq, struct kmp_output *out)
156 {
157         for (; out; out = out->next)
158                 if (!freq[out->id].occur++)
159                         add_tail(nonzeroes, &freq[out->id].n);
160 }
161
162 static inline byte *
163 kmp_search_internal(struct kmp *kmp, byte *str, uns len, struct list *nonzeroes, struct kmp_result *freq, struct kmp_output *out)
164   /* For every found string with id ID, it increments freq[ID].
165    * Also, it finds the longest among the leftmost matches.  */
166 {
167         byte *str_end = str + len;
168         kmp_state_t s = 0;
169         kmp_char_t c = CONTROL_CHAR;
170         struct kmp_transition tr, **prev;
171         byte eof = 0;
172         if (kmp->words_len <= 1)
173                 return NULL;
174         //TRACE(20, "kmp.c: Searching string %s", str);
175         byte *largest_match = NULL;
176         while (1)
177         {
178                 tr.from = s;
179                 tr.c = c;
180                 prev = transition_search(&kmp->g, &tr);
181                 while (tr.from && !*prev)
182                 {
183                         tr.from = kmp->f[ tr.from ];
184                         prev = transition_search(&kmp->g, &tr);
185                 }
186                 s = *prev ? (*prev)->to : 0;
187                 if (nonzeroes)
188                         add_result(nonzeroes, freq, kmp->out[s]);
189                 /* Beware that out->len is measured in modified characters of
190                  * the search pattern, hence it is not very reliable if you use
191                  * unaccenting.  */
192                 struct kmp_output *kout = kmp->out[s];
193                 if (kout && (!largest_match || str - kout->len <= largest_match))
194                 {
195                         largest_match = str - kout->len;
196                         if (out)
197                                 *out = *kout;
198                 }
199                 if (eof)
200                         break;
201                 if (str >= str_end)
202                         c = 0;
203                 else
204                         kmp_get_char((const byte **)&str, &c, kmp->modify_flags);
205                 if (!c)
206                 {
207                         /* Insert CONTROL_CHAR at the beginning and at the end too.  */
208                         c = CONTROL_CHAR;
209                         eof = 1;
210                 }
211         }
212         return largest_match;
213 }
214
215 static inline void
216 kmp_search(struct kmp *kmp, const byte *str, struct list *nonzeroes, struct kmp_result *freq)
217 {
218         kmp_search_internal(kmp, (byte*) str, strlen(str), nonzeroes, freq, NULL);
219 }
220
221 static inline byte *
222 kmp_find_first(struct kmp *kmp, byte *str, uns len, struct kmp_output *out)
223 {
224         return kmp_search_internal(kmp, str, len, NULL, NULL, out);
225 }
226
227 #endif