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 KMP_GET_RAW
  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, const byte *str, uns id)
  69 {
  70         struct kmp_transition tr = { .next=NULL, .from=0 }, **prev;
  71         struct kmp_output *new_out;
  72         const byte *orig_str = str;
  73         uns len = 0;
  74         kmp_char_t c = 'a';
  75
  76         TRACE(20, "kmp.c: Entering string %s", str);
  77         kmp_get_char(&str, &c, 0);
  78         len++;
  79         if (!c)
  80                 return;
  81         while (c)
  82         {
  83                 tr.c = c;
  84                 prev = transition_search(&kmp->g, &tr);
  85                 if (!*prev)
  86                         break;
  87                 tr.from = (*prev)->to;
  88                 kmp_get_char(&str, &c, 0);
  89                 len++;
  90         }
  91         while (c)
  92         {
  93                 *prev = mp_alloc_zero(kmp->mp, sizeof(struct kmp_transition));
  94                 tr.to = kmp->g.count++;
  95                 **prev = tr;
  96                 add_tail(kmp->g.sons + tr.from, &(*prev)->n);
  97                 init_list(kmp->g.sons + tr.to);
  98                 kmp_get_char(&str, &c, 0);
  99                 len++;
 100                 tr.from = tr.to;
 101                 tr.c = c;
 102                 prev = transition_search(&kmp->g, &tr);
 103                 ASSERT(!*prev);
 104         }
 105         if (kmp->out[tr.from])
 106                 TRACE(5, "kmp.c: string %s is inserted more than once", orig_str);
 107         new_out = new_output(kmp, id, len-1);
 108         merge_output(kmp->out + tr.from, new_out);
 109 }
 110
 111 static void
 112 construct_f_out(struct kmp *kmp)
 113 {
 114         kmp_state_t *fifo;
 115         int read, write;
 116         struct kmp_transition *son;
 117
 118         fifo = alloca(kmp->words_len * sizeof(kmp_state_t));
 119         read = write = 0;
 120         kmp->f[0] = 0;
 121         WALK_LIST(son, kmp->g.sons[0])
 122         {
 123                 ASSERT(son->from == 0);
 124                 kmp->f[son->to] = 0;
 125                 fifo[write++] = son->to;
 126         }
 127         while (read != write)
 128         {
 129                 kmp_state_t r, s, t;
 130                 r = fifo[read++];
 131                 WALK_LIST(son, kmp->g.sons[r])
 132                 {
 133                         struct kmp_transition tr, **prev;
 134                         ASSERT(son->from == r);
 135                         tr.c = son->c;
 136                         s = son->to;
 137                         fifo[write++] = s;
 138                         t = kmp->f[r];
 139                         while (1)
 140                         {
 141                                 tr.from = t;
 142                                 prev = transition_search(&kmp->g, &tr);
 143                                 if (*prev || !tr.from)
 144                                         break;
 145                                 t = kmp->f[t];
 146                         }
 147                         kmp->f[s] = *prev ? (*prev)->to : 0;
 148                         merge_output(kmp->out + s, kmp->out[ kmp->f[s] ]);
 149                 }
 150         }
 151 }
 152
 153 void
 154 kmp_build(struct kmp *kmp)
 155 {
 156         ASSERT(kmp->g.count <= kmp->words_len);
 157         construct_f_out(kmp);
 158         if (kmp->words_len > 1)
 159                 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);
 160 }