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