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