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