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_RAW(pos, c, flags) c=*pos++
  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, const byte *str, uns id);
  90 void kmp_build(struct kmp *kmp);
  91
  92 static inline void
  93 kmp_get_char(const byte **str, 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 KMP_GET_RAW to read its input.
 114          */
 115         byte buf[3*strlen(str)+1], *str2 = buf;
 116         kmp_char_t c = 0;
 117         do
 118         {
 119                 kmp_get_char(&str, &c, kmp->modify_flags);
 120                 str2 = utf8_put(str2, c);
 121         }
 122         while (c);
 123         kmp_enter_raw_string(kmp, buf, id);
 124 }
 125
 126 static inline uns
 127 transition_hashf(struct kmp_transitions *l UNUSED, struct kmp_transition *tr)
 128 {
 129         return tr->from + (tr->c << 16);
 130 }
 131
 132 static inline int
 133 transition_compare(struct kmp_transition *a, struct kmp_transition *b)
 134 {
 135         if (a->from == b->from && a->c == b->c)
 136                 return 0;
 137         else
 138                 return 1;
 139 }
 140
 141 static inline struct kmp_transition **
 142 transition_search(struct kmp_transitions *l, struct kmp_transition *tr)
 143 {
 144         uns hf = transition_hashf(l, tr) % l->hash_size;
 145         struct kmp_transition **last = l->chain + hf;
 146         while (*last && transition_compare(*last, tr))
 147                 last = &(*last)->next;
 148         ASSERT(last);
 149         return last;
 150 }
 151
 152 static inline void
 153 add_result(struct list *nonzeroes, struct kmp_result *freq, struct kmp_output *out)
 154 {
 155         for (; out; out = out->next)
 156                 if (!freq[out->id].occur++)
 157                         add_tail(nonzeroes, &freq[out->id].n);
 158 }
 159
 160 static inline byte *
 161 kmp_search_internal(struct kmp *kmp, byte *str, uns len, struct list *nonzeroes, struct kmp_result *freq, struct kmp_output *out)
 162   /* For every found string with id ID, it increments freq[ID].
 163    * Also, it finds the longest among the leftmost matches.  */
 164 {
 165         byte *str_end = str + len;
 166         kmp_state_t s = 0;
 167         kmp_char_t c = KMP_CONTROL_CHAR;
 168         struct kmp_transition tr, **prev;
 169         byte eof = 0;
 170         if (kmp->words_len <= 1)
 171                 return NULL;
 172         //TRACE(20, "kmp.c: Searching string %s", str);
 173         byte *largest_match = NULL;
 174         while (1)
 175         {
 176                 tr.from = s;
 177                 tr.c = c;
 178                 prev = transition_search(&kmp->g, &tr);
 179                 while (tr.from && !*prev)
 180                 {
 181                         tr.from = kmp->f[ tr.from ];
 182                         prev = transition_search(&kmp->g, &tr);
 183                 }
 184                 s = *prev ? (*prev)->to : 0;
 185                 if (nonzeroes)
 186                         add_result(nonzeroes, freq, kmp->out[s]);
 187                 /* Beware that out->len is measured in modified characters of
 188                  * the search pattern, hence it is not very reliable if you use
 189                  * unaccenting.  */
 190                 struct kmp_output *kout = kmp->out[s];
 191                 if (kout && (!largest_match || str - kout->len <= largest_match))
 192                 {
 193                         largest_match = str - kout->len;
 194                         if (out)
 195                                 *out = *kout;
 196                 }
 197                 if (eof)
 198                         break;
 199                 if (str >= str_end)
 200                         c = 0;
 201                 else
 202                         kmp_get_char((const byte **)&str, &c, kmp->modify_flags);
 203                 if (!c)
 204                 {
 205                         /* Insert KMP_CONTROL_CHAR at the beginning and at the end too.  */
 206                         c = KMP_CONTROL_CHAR;
 207                         eof = 1;
 208                 }
 209         }
 210         return largest_match;
 211 }
 212
 213 static inline void
 214 kmp_search(struct kmp *kmp, const byte *str, struct list *nonzeroes, struct kmp_result *freq)
 215 {
 216         kmp_search_internal(kmp, (byte*) str, strlen(str), nonzeroes, freq, NULL);
 217 }
 218
 219 static inline byte *
 220 kmp_find_first(struct kmp *kmp, byte *str, uns len, struct kmp_output *out)
 221 {
 222         return kmp_search_internal(kmp, str, len, NULL, NULL, out);
 223 }
 224
 225 #endif