lib/kmp.c

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