lib/kmp.c

   1 /*
   2  *      Knuth-Morris-Pratt's search automat for N given strings
   3  *              (taken from ad2 super-server and pruned :-)
   4  *
   5  *      (c) 1999--2005, Robert Spalek <robert@ucw.cz>
   6  */
   7
   8 #include "lib/lib.h"
   9 #include "lib/mempool.h"
  10 #include "lib/lists.h"
  11 #include "sherlock/tagged-text.h"
  12 #include "lib/unicode.h"
  13
  14 #define KMP_TRANSLATE(new_c, c, flags)  NO_TRANSLATE(new_c, c, flags)
  15 #include "lib/kmp.h"
  16
  17 #include <stdlib.h>
  18 #include <stdio.h>
  19 #include <string.h>
  20 #include <alloca.h>
  21
  22 #define TRACE(level, mask...)   if (0) fprintf(stderr, mask)
  23
  24 struct kmp *
  25 kmp_new(struct mempool *mp, int words_len, uns modify_flags)
  26 {
  27         struct kmp *kmp = mp_alloc_zero(mp, sizeof(struct kmp));
  28         kmp->mp = mp;
  29         kmp->modify_flags = modify_flags;
  30         kmp->words_len = words_len;
  31         int size = words_len;
  32         kmp->g.count = 1;
  33         kmp->g.size = size;
  34         kmp->g.sons = mp_alloc_zero(mp, size * sizeof(struct list));
  35         init_list(kmp->g.sons + 0);
  36         if (words_len > 1)
  37                 size = words_len * fls(words_len);
  38         else
  39                 size = 1;
  40         kmp->g.hash_size = size;
  41         kmp->g.chain = mp_alloc_zero(mp, size * sizeof(struct kmp_transition *));
  42         kmp->f = mp_alloc_zero(mp, words_len * sizeof(kmp_state_t));
  43         kmp->out = mp_alloc_zero(mp, words_len * sizeof(struct kmp_output *));
  44         return kmp;
  45 }
  46
  47 /*
  48  * The only merge operation is that son includes output of his father (and also
  49  * his father,...), so we can merge the link-lists.
  50  */
  51 static void
  52 merge_output(struct kmp_output **target, struct kmp_output *src)
  53 {
  54         while (*target)
  55                 target = &(*target)->next;
  56         *target = src;
  57 }
  58
  59 static struct kmp_output *
  60 new_output(struct kmp *kmp, uns id, uns len)
  61 {
  62         struct kmp_output *out = mp_alloc(kmp->mp, sizeof(struct kmp_output));
  63         out->next = NULL;
  64         out->id = id;
  65         out->len = len;
  66         return out;
  67 }
  68
  69 void
  70 kmp_enter_raw_string(struct kmp *kmp, const byte *str, uns id)
  71 {
  72         struct kmp_transition tr = { .next=NULL, .from=0 }, **prev;
  73         struct kmp_output *new_out;
  74         const byte *orig_str = str;
  75         uns len = 0;
  76         kmp_char_t c = 'a';
  77
  78         TRACE(20, "kmp.c: Entering string %s", str);
  79         kmp_get_char(&str, &c, 0);
  80         len++;
  81         if (!c)
  82                 return;
  83         while (c)
  84         {
  85                 tr.c = c;
  86                 prev = transition_search(&kmp->g, &tr);
  87                 if (!*prev)
  88                         break;
  89                 tr.from = (*prev)->to;
  90                 kmp_get_char(&str, &c, 0);
  91                 len++;
  92         }
  93         while (c)
  94         {
  95                 *prev = mp_alloc_zero(kmp->mp, sizeof(struct kmp_transition));
  96                 tr.to = kmp->g.count++;
  97                 **prev = tr;
  98                 add_tail(kmp->g.sons + tr.from, &(*prev)->n);
  99                 init_list(kmp->g.sons + tr.to);
 100                 kmp_get_char(&str, &c, 0);
 101                 len++;
 102                 tr.from = tr.to;
 103                 tr.c = c;
 104                 prev = transition_search(&kmp->g, &tr);
 105                 ASSERT(!*prev);
 106         }
 107         if (kmp->out[tr.from])
 108                 TRACE(5, "kmp.c: string %s is inserted more than once", orig_str);
 109         new_out = new_output(kmp, id, len-1);
 110         merge_output(kmp->out + tr.from, new_out);
 111 }
 112
 113 static void
 114 construct_f_out(struct kmp *kmp)
 115 {
 116         kmp_state_t *fifo;
 117         int read, write;
 118         struct kmp_transition *son;
 119
 120         fifo = alloca(kmp->words_len * sizeof(kmp_state_t));
 121         read = write = 0;
 122         kmp->f[0] = 0;
 123         WALK_LIST(son, kmp->g.sons[0])
 124         {
 125                 ASSERT(son->from == 0);
 126                 kmp->f[son->to] = 0;
 127                 fifo[write++] = son->to;
 128         }
 129         while (read != write)
 130         {
 131                 kmp_state_t r, s, t;
 132                 r = fifo[read++];
 133                 WALK_LIST(son, kmp->g.sons[r])
 134                 {
 135                         struct kmp_transition tr, **prev;
 136                         ASSERT(son->from == r);
 137                         tr.c = son->c;
 138                         s = son->to;
 139                         fifo[write++] = s;
 140                         t = kmp->f[r];
 141                         while (1)
 142                         {
 143                                 tr.from = t;
 144                                 prev = transition_search(&kmp->g, &tr);
 145                                 if (*prev || !tr.from)
 146                                         break;
 147                                 t = kmp->f[t];
 148                         }
 149                         kmp->f[s] = *prev ? (*prev)->to : 0;
 150                         merge_output(kmp->out + s, kmp->out[ kmp->f[s] ]);
 151                 }
 152         }
 153 }
 154
 155 void
 156 kmp_build(struct kmp *kmp)
 157 {
 158         ASSERT(kmp->g.count <= kmp->words_len);
 159         construct_f_out(kmp);
 160         if (kmp->words_len > 1)
 161                 TRACE(0, "Built KMP with modify flags %d for total words len %d, it has %d nodes", kmp->modify_flags, kmp->words_len, kmp->g.count);
 162 }